Back to Search
Start Over
Two-Dimensional Limited Context Restarting Automata.
- Source :
-
Fundamenta Informaticae . 2016, Vol. 148 Issue 3-4, p309-340. 32p. - Publication Year :
- 2016
-
Abstract
- Motivated by possible machine learning of picture languages, we introduce a new twodimensional 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01692968
- Volume :
- 148
- Issue :
- 3-4
- Database :
- Academic Search Index
- Journal :
- Fundamenta Informaticae
- Publication Type :
- Academic Journal
- Accession number :
- 120464840
- Full Text :
- https://doi.org/10.3233/FI-2016-1437