Milan Seminar on Automata and Formal Languages

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.