@INPROCEEDINGS{MraOtt14sofsem,
  author = {František Mráz and Friedrich Otto},
  title = {Ordered Restarting Automata for Picture Languages},
  booktitle = {SOFSEM 2014: Theory and Practice of Computer Science},
  year = {2014},
  editor = {Viliam Geffert and Bart Preneel and Branislav Rovan and Julius Stuller
    and A Min Tjoa},
  volume = {8327},
  series = {Lecture Notes in Computer Science},
  pages = {431--442},
  address = {Berlin, Heidelberg},
  publisher = {Springer},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  ee = {http://dx.doi.org/10.1007/978-3-319-04298-5_38},
  isbn = {978-3-319-04297-8},
  owner = {František Mráz},
  timestamp = {2015.01.24}
  abstract = {We introduce a two-dimensional variant of the restarting automaton with window size three-by-three for processing rectangular pictures. In each rewrite step such an automaton can only replace the symbol in the middle position of its window by a symbol that is smaller with respect to a fixed ordering on the tape alphabet. When restricted to one-dimensional inputs (that is, words) the deterministic variant of these ordered restarting automata only accepts regular languages, while the nondeterministic one can accept some languages that are not even context-free. We then concentrate on the deterministic two-dimensional ordered restarting automaton, showing that it is quite expressive as it can simulate the deterministic sgraffito automaton, and we present some closure and non-closure properties for the class of picture languages accepted by these automata.}
}