On some 2D grammars
In the framework of the "Milan Seminar on Automata and Formal Languages" series, which provides monthly seminars at UniversitÓ di Milano, UniversitÓ di Milano-Bicocca and Politecnico di Milano, on Thursday, May 31st at 4:00 p.m., in the PT1 room of the DEI, Marcello Bersani will speak about "On some 2D grammars".
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.