On some Classes of 2D Languages and their Relations

On some Classes of 2D Languages and their Relations
Marcello Maria Bersani
PhD Student

DEI - Seminari Room
November 19th, 2010


In this talk we compare various classes of bi-dimensional languages. Many formal models have been proposed to recognize or to generate bidimensional words; similarly to the classical theory of one-dimension languages, different approaches can be defined.
We focus the analysis on Subramanian, Regional tile grammars and Prusa Grammars. Nevertheless they were been proposed as a generalization of string CF languages, their expressiveness results to be different. This work refines and tries to clarify the relationship between these classes and shows some considerations about closure properties of Subramanian's languages.

Marcello Maria Bersani

Research Area:
Advanced software architectures and methodologies