Reversibility of computations in graph-walking automata
From MaRDI portal
Publication:2216129
DOI10.1016/j.ic.2020.104631zbMath1496.68176OpenAlexW4206628004MaRDI QIDQ2216129
Alexander Okhotin, Michal Kunc
Publication date: 15 December 2020
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2020.104631
Related Items
Homomorphisms on graph-walking automata ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ State complexity of transforming graph-walking automata to halting, returning and reversible ⋮ Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound ⋮ Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs ⋮ A time to cast away stones ⋮ Deterministic one-way simulation of two-way deterministic finite automata over small alphabets ⋮ State complexity of union and intersection on graph-walking automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Size complexity of rotating and sweeping automata
- Complexity of multi-head finite automata: origins and directions
- Reversible simulation of space-bounded computations
- The equivalence problem of multitape finite automata
- Invertible cellular automata: A review
- Tree-walking automata cannot be determinized
- Complementing deterministic tree-walking automata
- Halting space-bounded computations
- Lower bounds on the size of sweeping automata
- Space bounded computations: Review and new separation results
- Complexity results for two-way and multi-pebble automata and their logics
- Reversible space equals deterministic space
- Reversible pushdown automata
- One-way reversible multi-head finite automata
- Graph exploration by a finite automaton
- A survey of two-dimensional automata theory
- Complementing two-way finite automata
- A Lower Bound For Reversible Automata
- Time and space bounds for reversible simulation
- Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
- Reversibility in space-bounded computation
- Space-efficient Basic Graph Algorithms
- Translation from classical two-way automata to pebble two-way automata
- A Survey on Picture-Walking Automata
- Two-Way Reversible Multi-Head Finite Automata
- A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads
- Expressive Power of Pebble Automata
- Tree-Walking Automata Do Not Recognize All Regular Languages
- Irreversibility and Heat Generation in the Computing Process
- Time/Space Trade-Offs for Reversible Computation
- Parallel and two-way automata on directed ordered acyclic graphs
- Automata and Labyrinths
- Restarting automata
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
- Developments in Language Theory
- Some Results on Tape-Bounded Turing Machines
- Translations on a context free grammar
- Logical Reversibility of Computation
This page was built for publication: Reversibility of computations in graph-walking automata
