State complexity of transforming graph-walking automata to halting, returning and reversible
From MaRDI portal
Publication:2687992
DOI10.1016/J.IC.2023.105011zbMATH Open1506.68048OpenAlexW4319311375MaRDI QIDQ2687992FDOQ2687992
Authors: Olga Martynova, Alexander Okhotin 
Publication date: 7 March 2023
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2023.105011
Recommendations
- Reversibility of computations in graph-walking automata
- Graph-walking automata: from whence they come, and whither they are bound
- Reversibility of computations in graph-walking automata
- Finite automata with undirected state graphs
- State complexity of reversals of deterministic finite automata with output
Cites Work
- Irreversibility and Heat Generation in the Computing Process
- Graph exploration by a finite automaton
- Halting space-bounded computations
- Complementing two-way finite automata
- Complementing deterministic tree-walking automata
- Automata and Labyrinths
- Tree-walking automata cannot be determinized
- Tight bounds for undirected graph exploration with pebbles and multiple agents
- A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads
- Reversible space equals deterministic space
- Reversibility of computations in graph-walking automata
Cited In (6)
- Reversibility of computations in graph-walking automata
- Reversibility of computations in graph-walking automata
- Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
- Homomorphisms and inverse homomorphisms on graph-walking automata
- State complexity of union and intersection on graph-walking automata
- Graph-walking automata: from whence they come, and whither they are bound
This page was built for publication: State complexity of transforming graph-walking automata to halting, returning and reversible
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2687992)
