Abstract: Alessandra Cherubini |
GRAMATICAL APPROACH TO 2D LANGUAGE
Since the early days of formal language theory, considerable research effort has been spent towards the objective of extending grammar based approaches from one to two dimensions (2D), i.e., from string languages to picture languages. Several classes of picture grammars, that variously extend context-free string grammars in two dimensions, Have been proposed in the course of years. Most of them are Based on rules that rewrite arrays of pixels. Such grammars can be unified and extended using a tiling based approach, whereby the right part of a rule is normalized by means of a finite set of permitted tiles. My talk focuses on a simple type of tiling, named regional, and on the corresponding regional tile grammars. Such grammars include both Siromoney’s (or Matz’s) Kolam grammars and their generalization by Prusa, as well as Drewes’s grid grammars. Moreover regionally defined pictures can be recognized with polynomial time complexity by an algorithm extending the CKY one for strings. Regional tile grammars are incomparable with Giammarresi-Restivo tiling systems. These facts suggest the following question: Is it possible to extend Chomsky's hierarchy from 1D to 2D? |