State complexity of transforming graph-walking automata to halting, returning and reversible
From MaRDI portal
Publication:2687992
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
- A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads
- Automata and Labyrinths
- Complementing deterministic tree-walking automata
- Complementing two-way finite automata
- Graph exploration by a finite automaton
- Halting space-bounded computations
- Irreversibility and Heat Generation in the Computing Process
- Reversibility of computations in graph-walking automata
- Reversible space equals deterministic space
- Tight bounds for undirected graph exploration with pebbles and multiple agents
- Tree-walking automata cannot be determinized
Cited in
(6)- State complexity of union and intersection on graph-walking automata
- 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
- 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)
