Affiliations: Faculty of Mathematics and Physics, Charles University in Prague, Malostranské nám, 25, 118 00 Prague 1, Czech Republic. [email protected]; [email protected]
Correspondence:
[*]
Address for correspondence: Department of Software and Computer Science Education, Faculty of Mathematics and Physics Charles University in Prague, Malostranské nám, 25, 118 00 Prague 1, Czech Republic. The first author was supported by the Science Foundation of the Czech Republic under the project P202/10/1333.
Correspondence:
[†]
The second author was supported by the Science Foundation of the Czech Republic under the project 15-04960S.
Abstract: Motivated by possible machine learning of picture languages, we introduce a new two-dimensional automaton called two-dimensional limited context restarting automaton. Our model is a simplification of the two-dimensional restarting tiling automaton, from which it differs in that it does not require to scan input pictures in a fixed order. We show that the two-dimensional limited context restarting automaton is equally powerful as the two-dimensional sgraffito automaton. Moreover, the correctness preserving version of the new model, while still being nondeterministic, is equivalent to the deterministic sgraffito automaton. However, the property of being correctness preserving is not even semi-decidable for two-dimensional limited context restarting automata.
