Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs

2022/12/05 by Martynova, Olga
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2212.02380

Abstract

This paper proves the decidability of the emptiness problem for two models which recognize 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.

Related

• The Emptiness Problem for Tree Automata with at Least One Disequality Constraint is NP-hard
• Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
• Emptiness of zero automata is decidable
• Relations between automata and the simple k-path problem
• Completely reachable automata: an interplay between automata, graphs, and trees