Publication at Faculty of Mathematics and Physics |
2014
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.