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

DOI10.1016/J.IC.2023.105127arXiv2212.02380OpenAlexW4389166006MaRDI QIDQ6178459FDOQ6178459

Authors: Olga Martynova 

Publication date: 18 January 2024

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

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.

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)