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

Autor:	Martynova, Olga
Rok vydání:	2022
Předmět:	Computer Science - Formal Languages and Automata Theory
Druh dokumentu:	Working Paper
Popis:	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. Comment: 29 pages, 4 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2212.02380 Zobrazit plný text záznamu View this record from Arxiv