Seminario: "On some 2D grammars", relatore Marcello Bersani, 31 maggio 2012

On some 2D grammars

Marcello Bersani (Politecnico di Milano)

giovedì 31 Maggio 2012 - 15.30 Aula TBA, Dipartimento di Elettronica e Informatica, Politecnico di Milano


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 classes proposed turns to be necessary. In this paper, we study in detail closure properties of (regular) pure 2D context-free grammars (R)P2DCFG, for which we also prove the parsing is NP-hard. Moreover, we draw some comparisons with other interesting picture grammars like regional tile grammars, Prusa grammars and local languages, establishing their mutual relationship with respect to expressiveness.