69
Views
9
CrossRef citations to date
0
Altmetric
Section A

Expressiveness and complexity of regular pure two-dimensional context-free languages

, &
Pages 1708-1733 | Received 15 Apr 2012, Accepted 13 Mar 2013, Published online: 14 May 2013
 

Abstract

Picture languages generalize classical string languages to two-dimensional arrays. Several approaches have been proposed during the years; consequently, a general classification and a detailed comparison of the proposed classes turn to be necessary. In this paper, we study some closure properties of (regularly controlled) pure two-dimensional context-free grammars, for which we also prove that the parsing is NP-hard. Moreover, we draw some comparisons with other interesting picture grammars like (regional) tile grammars, Pruša grammars and local languages, clarifying, in some cases, their mutual relationship with respect to expressiveness.

2010 AMS Subject Classifications:

ACM Computing Classification System Code:

Acknowledgements

The authors are very grateful to the anonymous referee and would like to deeply thank him/her for precious and useful comments which improved their work and helped to clarify the paper.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.