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

DOI10.1016/J.IC.2023.105127MaRDI QIDQ6178459zbMATH OpenOpenAlexFDO

Authors Olga Martynova

Publication date 18 January 2024

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.02380

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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.

Cites work

• scientific article; zbMATH DE number 176754 (Why is no real title available?)
• Automata and Labyrinths
• Automaten in planaren Graphen
• Graph exploration by a finite automaton
• Reversibility of computations in graph-walking automata
• Some properties of two-dimensional on-line tessellation acceptors
• Space-bounded reducibility among combinatorial problems
• State complexity of transforming graph-walking automata to halting, returning and reversible
• State complexity of union and intersection on graph-walking automata
• Theory Is Forever
• Tree-Walking Automata
• Tree-walking automata cannot be determinized

This page was built for publication: Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6178459)