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, Prusa grammars and local languages, clarifying, in some cases, their mutual relationship with respect to expressiveness.

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

BERSANI, MARCELLO MARIA;FRIGERI, ACHILLE;CHERUBINI, ALESSANDRA
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, Prusa grammars and local languages, clarifying, in some cases, their mutual relationship with respect to expressiveness.
picture languages, pure grammars, rectangular arrays, two-dimensional grammars,
File in questo prodotto:
File Dimensione Formato  
Int_J_Comp_Math.pdf

Accesso riservato

Descrizione: Articolo principale
: Publisher’s version
Dimensione 9.03 MB
Formato Adobe PDF
9.03 MB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/801521
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact