Reversibility of computations in graph-walking automata
From MaRDI portal
Publication:2216129
DOI10.1016/J.IC.2020.104631zbMATH Open1496.68176OpenAlexW4206628004MaRDI QIDQ2216129FDOQ2216129
Authors: Michal Kunc, Alexander Okhotin 
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
Recommendations
- Reversibility of computations in graph-walking automata
- Graph-walking automata: from whence they come, and whither they are bound
- State complexity of transforming graph-walking automata to halting, returning and reversible
- Aspects of reversibility for classical automata
- One-way reversible multi-head finite automata
Cites Work
- Irreversibility and Heat Generation in the Computing Process
- Title not available (Why is that?)
- Logical Reversibility of Computation
- Graph exploration by a finite automaton
- Title not available (Why is that?)
- Reversibility in space-bounded computation
- Restarting automata
- Halting space-bounded computations
- Title not available (Why is that?)
- Translations on a context free grammar
- A survey on picture-walking automata
- Title not available (Why is that?)
- Complementing two-way finite automata
- Lower bounds on the size of sweeping automata
- Parallel and two-way automata on directed ordered acyclic graphs
- Size complexity of rotating and sweeping automata
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- Title not available (Why is that?)
- Complexity of multi-head finite automata: origins and directions
- Complementing deterministic tree-walking automata
- Tree-Walking Automata Do Not Recognize All Regular Languages
- Developments in Language Theory
- The equivalence problem of multitape finite automata
- Invertible cellular automata: A review
- Two-way reversible multi-head finite automata
- Automata and Labyrinths
- Tree-walking automata cannot be determinized
- Space bounded computations: Review and new separation results
- Some Results on Tape-Bounded Turing Machines
- Space-efficient basic graph algorithms
- Time/Space Trade-Offs for Reversible Computation
- Time and space bounds for reversible simulation
- Reversible simulation of space-bounded computations
- Title not available (Why is that?)
- Complexity results for two-way and multi-pebble automata and their logics
- Translation from classical two-way automata to pebble two-way automata
- Expressive Power of Pebble Automata
- Title not available (Why is that?)
- Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
- Reversible pushdown automata
- A survey of two-dimensional automata theory
- A lower bound for reversible automata
- One-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
- Reversible space equals deterministic space
- Reversible multi-head finite automata characterize reversible logarithmic space
Cited In (10)
- State complexity of transforming graph-walking automata to halting, returning and reversible
- Reversibility of computations in graph-walking automata
- 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
- Homomorphisms and inverse homomorphisms on graph-walking automata
- A time to cast away stones
- Homomorphisms on graph-walking automata
- Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
- 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: Reversibility of computations in graph-walking automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216129)
