Reversibility of computations in graph-walking automata
From MaRDI portal
(Redirected from Publication:2216129)
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
- scientific article; zbMATH DE number 4020506 (Why is no real title available?)
- scientific article; zbMATH DE number 176754 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 2086620 (Why is no real title available?)
- scientific article; zbMATH DE number 1408335 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3305030 (Why is no real title available?)
- A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads
- A lower bound for reversible automata
- A survey of two-dimensional automata theory
- A survey on picture-walking automata
- Automata and Labyrinths
- Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
- Complementing deterministic tree-walking automata
- Complementing two-way finite automata
- Complexity of multi-head finite automata: origins and directions
- Complexity results for two-way and multi-pebble automata and their logics
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- Developments in Language Theory
- Expressive Power of Pebble Automata
- Graph exploration by a finite automaton
- Halting space-bounded computations
- Invertible cellular automata: A review
- Irreversibility and Heat Generation in the Computing Process
- Logical Reversibility of Computation
- Lower bounds on the size of sweeping automata
- One-way reversible multi-head finite automata
- Parallel and two-way automata on directed ordered acyclic graphs
- Restarting automata
- Reversibility in space-bounded computation
- Reversible multi-head finite automata characterize reversible logarithmic space
- Reversible pushdown automata
- Reversible simulation of space-bounded computations
- Reversible space equals deterministic space
- Size complexity of rotating and sweeping automata
- Some Results on Tape-Bounded Turing Machines
- Space bounded computations: Review and new separation results
- Space-efficient basic graph algorithms
- The equivalence problem of multitape finite automata
- Time and space bounds for reversible simulation
- Time/Space Trade-Offs for Reversible Computation
- Translation from classical two-way automata to pebble two-way automata
- Translations on a context free grammar
- Tree-Walking Automata Do Not Recognize All Regular Languages
- Tree-walking automata cannot be determinized
- Two-way reversible multi-head finite automata
Cited in
(10)- Graph-walking automata: from whence they come, and whither they are bound
- 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
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)
