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 NPcomplete 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 twodimensional 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 onedimensional 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) 351369

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 NonClassical Models of Automata and Applications 321 (NCMA 2016),books@ocg.at, Proc.,
Österreichische Computer Gesellschaft, 259273

Mráz and Otto, F.:

Deterministic ordered restarting automata for picture languages
Acta Informatica 52 (2015) 593623

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 NonClassical Models of Automata and Applications 318 (NCMA 2015), Proc.,books@ocg.at,
Österreichische Computer Gesellschaft, 159176

Průša, D. and Mráz, F. and Otto, F.:

Twodimensional sgraffito automata,
RAIRO Informatique Théorique et Applications 48 (2014) 505539.

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),
318329.

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),
1641.

Mráz, F. and Otto, F.:

Extended twoway ordered restarting automata for picture languages
In Dediu, A.H., Martin Víde, C., SierraRodríguez, J.L., and Truthe B.,editors,
LATA 2014, Proc.,
Lecture Notes in Computer Science 8370,
Springer,
Heidelberg
(2014),
541552.

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),
431442.

Průša, D. and Mráz, F. and Otto, F.:

Comparing twodimensional onemarker automata to sgraffito automata,
In Konstantinidis, S.,editors,
CIAA 2013, Proc.,
Lecture Notes in Computer Science 7982,
Springer,
Berlin,
(2013),
268279.

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),
409419.