@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},
}