In the literature one finds many different types of grammars and automata for
defining classes of picture languages.
In particular, a lot of work has been devoted to defining and characterizing
a class of picture languages that would correspond to the class of regular 'string' languages
with respect to its various properties.
Eventually a kind of agreement has been reached that the class REC of 'recognizable
languages' introduced by Giammerresi and Restivo in 1992 is such a class
as it has various characterizations and nice closure properties.
Unfortunately, this class contains some NP-complete languages,
which means that in general the membership problem for a recognizable picture language can be quite
Motivated by that observation this project is directed at
finding a model of a two-dimensional automaton that has the following desirable properties:
- it should be conceptually simple, that is, it should be 'easy' to design automata
of this type for interesting example languages;
- it should be more powerful that the class DREC of 'deterministic recognizable languages,'
but when restricted to the one-dimensional case (that is, string languages),
then this model should only accept the regular languages;
- the membership problem should be decidable in polynomial time;
- the class of accepted picture languages should have nice closure properties.