@Article{Prusa-Mraz-Otto-RAIRO2014,
  UPDATE  = { 2014-12-16 },
  IS = { zkontrolovano 03 Feb 2015 },
author   = { Pr{\accent23 u}{\v s}a, Daniel and Mr{\' a}z, Franti{\v
                  s}ek and Otto, Friedrich },
  affiliation = {13133-NULL-NULL},
  title = {Two-dimensional Sgraffito automata},
  journal = {RAIRO - Theoretical Informatics and Applications},
volume   = { 48 },
number   = { 5 },
pages    = { 505--539 },
  publisher = {Cambridge University Press},
  address = {Cambridge, UK},
month    = { December },
  year = {2014},
issn     = { 0988-3754 },
  doi = {10.1051/ita/2014023},
url      = { http://www.rairo-ita.org/articles/ita/abs/2014/05/ita130054/ita130054.html },
  annote = {We present a new model of a two-dimensional computing
                  device called Sgraffito auto maton. In general, the
                  model is quite simple, which allows a clear design
                  of computations. When restricte d to one-dimensional
                  inputs, that is, strings, the Sgraffito automaton
                  does not exceed the power of finite- state automata.
                  On the other hand, for two-dimensional inputs, it
                  yields a family of picture languages with good
                  closure properties that strictly includes the class
                  REC? of recognizable picture languages. Th e
                  deterministic Sgraffito automata define a class of
                  picture languages that includes the class of dete
                  rministic recognizable picture languages DREC, the
                  class of picture languages that are accepted by
                  four-way a lternating automata, those that are
                  accepted by deterministic one-marker automata, and
                  the sudoku-determini stically recognizable picture
                  languages, but the membership problem for the
                  accepted languages is still deci dable in polynomial
                  time.  In addition, the deterministic Sgraffito
                  automata accept some unary picture languages that
                  are outside of the class REC.},
  keywords = {two-dimensional language, sgraffito automaton, bounded Turing machine, REC},
  project = {GACR P103/10/0783},
numpages    = { 35 },
}