"[8C9A20CFD3F9]" . . . "SOFSEM 2014: Theory and Practice of Computer Science" . "000342283300038" . "Berlin" . "11320" . . "10.1007/978-3-319-04298-5_38" . . "Ordered Restarting Automata for Picture Languages" . . "Springer-Verlag" . "Mr\u00E1z, Franti\u0161ek" . . "Nov\u00FD Smokovec, Slovakia" . "Otto, Friedrich" . "12"^^ . "picture language; ordered rewriting; restarting automaton"@en . . "Ordered Restarting Automata for Picture Languages"@en . . "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."@en . "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." . . "35077" . . "RIV/00216208:11320/14:10290063!RIV15-GA0-11320___" . . . . "Ordered Restarting Automata for Picture Languages" . "P(GAP103/10/0783)" . "2014-01-26+01:00"^^ . "RIV/00216208:11320/14:10290063" . . . "Ordered Restarting Automata for Picture Languages"@en . "0302-9743" . "http://link.springer.com/chapter/10.1007/978-3-319-04298-5_38" . . "2"^^ . "978-3-319-04297-8" . "1"^^ .