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

DOI10.1016/j.ic.2023.105127arXiv2212.02380OpenAlexW4389166006MaRDI QIDQ6178459

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)

Cites Work

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

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