Projekt 8 - Automata for Picture Languages

(Beginn 01/2013)

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 complex.

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.

Mitarbeiter:

Daniel Průša

Dr. František Mráz

Veröffentlichungen:

Průša, D. and Mráz, F. and Otto, F.:
Some classes of rational functions for pictures
RAIRO Informatique Théorique et Applications 50 (2016) 351-369
Mráz and Otto, F.:
Cyclically extended variants of Sgraffito and restarting automata for picture languages
In Bordihn H., Freund R., Nagy B. and Vaszil G., editors, Eighth Workshop on Non-Classical Models of Automata and Applications 321 (NCMA 2016),books@ocg.at, Proc., Österreichische Computer Gesellschaft, 259-273
Mráz and Otto, F.:
Deterministic ordered restarting automata for picture languages
Acta Informatica 52 (2015) 593-623
Průša, D. and Mráz, F. and Otto, F.:
On a class of rational functions for pictures
In Freund R., Holzer M., Moreira N. and Reis R.,editors, Seventh Workshop on Non-Classical Models of Automata and Applications 318 (NCMA 2015), Proc.,books@ocg.at, Österreichische Computer Gesellschaft, 159-176
Průša, D. and Mráz, F. and Otto, F.:
Two-dimensional sgraffito automata,
RAIRO Informatique Théorique et Applications 48 (2014) 505-539.
Otto, F.:
On the descriptional complexity of deterministic ordered restarting automata
In Jürgensen, H., Karhumäki, J., Okhotin, A.,editors, DCFS 2014, Proc., Lecture Notes in Computer Science 8614, Springer, Heidelberg, (2014), 318-329.
F. and Otto, F.:
Restarting automata for picture languages: A survey on recent developments
In Holzer, M. and Kutrib, M.,editors, CIAA 2014, Proc., Lecture Notes in Computer Science 8587, Springer, Heidelberg, (2014), 16-41.
Mráz, F. and Otto, F.:
Extended two-way ordered restarting automata for picture languages
In Dediu, A.-H., Martin Víde, C., Sierra-Rodríguez, J.L., and Truthe B.,editors, LATA 2014, Proc., Lecture Notes in Computer Science 8370, Springer, Heidelberg (2014), 541-552.
Mráz, F. and Otto, F.:
Ordered restarting automata for picture languages
In Geffert, V., Preneel, B., Rovan, B., Stuller, J. and Min Tjoa, A.,editors, SOFSEM 2014, Proc., Lecture Notes in Computer Science 8327, Springer, Heidelberg, (2014), 431-442.
Průša, D. and Mráz, F. and Otto, F.:
Comparing two-dimensional one-marker automata to sgraffito automata,
In Konstantinidis, S.,editors, CIAA 2013, Proc., Lecture Notes in Computer Science 7982, Springer, Berlin, (2013), 268--279.
Průša, D. and Mráz, F. and Otto, F.:
New results on deterministic sgraffito automata,
In Béal, M.-P. and Carton, O. editors, DLT 2013, Lecture Notes in Computer Science 7907 Springer, Berlin, (2013), 409--419.