@inproceedings{PrusaCIAA2013, IS = { zkontrolovano 24 Jan 2014 }, UPDATE = { 2013-09-25 }, author = {Pr{\r u}{\v s}a, Daniel and Mr{\' a}z, Franti{\v s}ek and Otto, Friedrich}, title = {Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata}, booktitle = {CIAA 2013: Proceedings of the 18th International Conference on Implementation and Application of Automata}, book_pages = {358}, series = {Lecture Notes in Computer Science}, editor = {Konstantinidis, Stavros}, isbn = {978-3-642-39273-3}, volume = {7982}, doi = {10.1007/978-3-642-39274-0_24}, url = {http://dx.doi.org/10.1007/978-3-642-39274-0_24}, annote = {We compare two types of automata for accepting picture languages to each other: the two-dimensional one-marker automaton and the sgraffito automaton. On the one hand, it is shown that deterministic sgraffito automata are strictly more powerful than deterministic two-dimensional one-marker automata. On the other hand, nondeterministic two-dimensional one-marker automata accept some picture languages that cannot be accepted by sgraffito automata. However, if nondeterministic two-dimensional one-marker automata were to accept all picture languages that are accepted by (deterministic) sgraffito automata, then the complexity classes NL (nondeterministic logarithmic space) and P (deterministic polynomial time) would coincide. Accordingly, it is likely that the classes of picture languages accepted by these two types of nondeterministic automata are incomparable under inclusion.}, publisher = {Springer-Verlag}, address = {Berlin, Heidelberg, Germany}, keywords = {picture languages, two-dimensional one-marker automaton, sgraffito automaton, recognizable picture languages}, pages = {268--279}, venue = {Halifax, Canada}, year = {2013}, month = {July}, day = {16-19}, project = {GACR P103/10/0783}, }