Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
- 30 November 2023
- journal article
- research article
- Published by Elsevier in Information and Computation
- Vol. 296
Abstract
No abstract availableAll Related Versions
Funding Information
- Russian Science Foundation (18-11-00100)
This publication has 10 references indexed in Scilit:
- State complexity of transforming graph-walking automata to halting, returning and reversibleInformation and Computation, 2023
- Reversibility of computations in graph-walking automataInformation and Computation, 2020
- Tree-walking automata cannot be determinizedTheoretical Computer Science, 2006
- Graph exploration by a finite automatonTheoretical Computer Science, 2005
- A CHARACTERIZATION OF RECOGNIZABLE PICTURE LANGUAGESInternational Journal of Pattern Recognition and Artificial Intelligence, 1994
- RECOGNIZABLE PICTURE LANGUAGESInternational Journal of Pattern Recognition and Artificial Intelligence, 1992
- Automaten in planaren GraphenActa Informatica, 1980
- Automata and LabyrinthsMathematische Nachrichten, 1978
- Some properties of two-dimensional on-line tessellation acceptorsInformation Sciences, 1977
- Space-bounded reducibility among combinatorial problemsJournal of Computer and System Sciences, 1975