Back to Search
Start Over
Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs.
- Source :
-
Information & Computation . Jan2024, Vol. 296, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- This paper proves the decidability of the emptiness problem for two models which recognize finite graphs: graph-walking automata, and tilings of graphs by star subgraphs (star automata). Furthermore, it is proved that the non-emptiness problem for graph-walking automata (that is, whether a given automaton accepts at least one graph) is NEXP-complete. For star automata, which generalize nondeterministic tree automata to the case of graphs, it is proved that their non-emptiness problem is NP-complete. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SUBGRAPHS
*NP-complete problems
*TILING (Mathematics)
*ROBOTS
Subjects
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 296
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 174791238
- Full Text :
- https://doi.org/10.1016/j.ic.2023.105127