@INPROCEEDINGS{OttMra14lata,
  author = {Friedrich Otto and František Mráz},
  title = {Extended Two-Way Ordered Restarting Automata for Picture Languages},
  booktitle = {Language and Automata Theory and Applications -- 8th International
    Conference, LATA 2014},
  year = {2014},
  editor = {Adrian Horia Dediu and Carlos Mart\'{\i}n-Vide and Jos{\'e} Luis
    Sierra-Rodr\'{\i}guez and Bianca Truthe},
  volume = {8370},
  series = {Lecture Notes in Computer Science},
  pages = {541--552},
  address = {Berlin, Heidelberg},
  publisher = {Springer},
  ee = {http://dx.doi.org/10.1007/978-3-319-04921-2_44},
  isbn = {978-3-319-04920-5},
  owner = {František Mráz},
  timestamp = {2015.01.24},
  abstract = {We introduce a two-dimensional variant of the deterministic restarting automaton for processing rectangular pictures. Our device has a window of size three-by-three, in a rewrite step it can only replace the symbol in the central position of its window by a symbol that is smaller with respect to a fixed ordering on the tape alphabet, and it can only perform (extended) move-right and move-down steps. This automaton is strictly more expressive than the deterministic Sgraffito automaton, but its word problem can still be solved in polynomial time, and when restricted to one-dimensional input, it only accepts the regular languages.}
}