Two-Dimensional Limited Context Restarting Automata

摘要

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.