Restarting Automata for Picture Languages: A Survey on Recent Developments

Much work has been done to obtain classes of picture languages that would correspond to the classes of the Chomsky hierarchy for string languages, and finally the class

REC

of recognizable picture languages has been agreed on as the class that corresponds to the ‘regular string languages.’ This class has several nice characterizations in terms of regular expressions, tiling automata, and on-line tesselation automata, and it has nice closure properties, but it also has two main drawbacks: all its characterizations are highly nondeterministic in nature, and it contains languages that are NP-complete. Consequentially, various deterministic subclasses of

REC

have been defined. Mainly, however, these definitions are quite complex, and it is not clear which of the resulting classes should be considered as ‘the’ class of deterministic recognizable picture languages. Here we present some recent developments obtained in a research project that aims at finding a deterministic model of a two-dimensional automaton that has the following desirable properties:

the automaton should be conceptually simple,

the class of languages accepted should be as large as possible,

it should have nice closure properties,

the membership problem for each of these languages should be solvable in polynomial time,

but when restricted to one-row pictures (that is, strings), only the regular languages should be accepted.

In the course of the project, several types of two-dimensional automata have been defined and investigated. Here these types of automata and the classes of picture languages accepted by them are compared to each other and to the classes

REC

and

DREC

, and their closure properties and algorithmic properties are considered.