@ARTICLE{PruMraOtt14rairo,
  author = {Průša,Daniel and Mráz,František and Otto,Friedrich},
  title = {Two-dimensional Sgraffito automata},
  journal = {RAIRO -- Theoretical Informatics and Applications},
  year = {2014},
  volume = {48},
  pages = {505--539},
  month = {12},
  note = {impact factor 0.179},
  abstract = {We present a new model of a two-dimensional computing device called
    Sgraffito automaton. In general, the model is quite simple, which
    allows a clear design of computations. When restricted 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. The deterministic Sgraffito automata define a
    class of picture languages that includes the class of deterministic
    recognizable picture languages DREC, the class of picture languages
    that are accepted by four-way alternating automata, those that are
    accepted by deterministic one-marker automata, and the sudoku-deterministically
    recognizable picture languages, but the membership problem for the
    accepted languages is still decidable in polynomial time. In addition,
    the deterministic Sgraffito automata accept some unary picture languages
    that are outside of the class REC.},
  doi = {10.1051/ita/2014023},
  issn = {1290-385X},
  issue = {05},
  numpages = {35},
  url = {http://www.rairo-ita.org/article_S098837541400023X}
}