"Extended Two-Way Ordered Restarting Automata for Picture Languages" . "Lecture Notes in Computer Science" . . "12"^^ . . . . "Otto, Friedrich" . "[B99FA7452C6A]" . . . . . . "16182" . "Extended Two-Way Ordered Restarting Automata for Picture Languages" . "http://link.springer.com/chapter/10.1007/978-3-319-04921-2_44" . "2014-03-10+01:00"^^ . . . . . "Extended Two-Way Ordered Restarting Automata for Picture Languages"@en . "0302-9743" . "Madrid, \u0160pan\u011Blsko" . "1"^^ . "Mr\u00E1z, Franti\u0161ek" . "RIV/00216208:11320/14:10290136!RIV15-GA0-11320___" . "10.1007/978-3-319-04921-2_44" . "P(GAP103/10/0783), P(GAP202/10/1333)" . "2"^^ . . "RIV/00216208:11320/14:10290136" . "Berlin" . . "Extended Two-Way Ordered Restarting Automata for Picture Languages"@en . "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." . . . "picture language; ordered rewriting; restarting automaton"@en . "978-3-319-04920-5" . "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."@en . "Springer-Verlag" . "11320" .