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

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.

Keywords:

• picture languages
• pure grammars
• rectangular arrays
• two-dimensional grammars

2010 AMS Subject Classifications:

• 68Q15
• 68Q25
• 68Q42
• 68R99

ACM Computing Classification System Code:

• F.4.2

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.