Reversible and Irreversible Computations of Deterministic Finite-State Devices

DOI10.1007/978-3-662-48057-1_3zbMath1465.68158OpenAlexW2130741488MaRDI QIDQ2946323

Martin Kutrib

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48057-1_3

zbMATH Keywords

minimalitydecidabilityreversibilityclosure propertiesfinite-state devicesqueue and pushdown storage

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Other nonclassical models of computation (68Q09)

Related Items (9)

Reversible top-down syntax analysis ⋮ Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata ⋮ Weakly and Strongly Irreversible Regular Languages ⋮ Reversible Top-Down Syntax Analysis ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finite automata with undirected state graphs ⋮ Concise Representations of Reversible Automata ⋮ Minimal and Reduced Reversible Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversible simulation of one-dimensional irreversible cellular automata
• Real-time reversible iterative arrays
• Reversible computing and cellular automata -- a survey
• Fast reversible language recognition using cellular automata
• On the efficient construction of quasi-reversible automata for reversible languages
• QRT FIFO automata, breadth-first grammars and their relations
• Learning approximately regular languages with reversible languages
• Reversibility and surjectivity problems of cellular automata
• Reversible space equals deterministic space
• Reversible pushdown automata
• Über einen Automaten mit Pufferspeicherung
• A Lower Bound For Reversible Automata
• A Hierarchy of Fast Reversible Turing Machines
• Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
• Aspects of Reversibility for Classical Automata
• Reversible Limited Automata
• A Simple and Efficient Universal Reversible Turing Machine
• Two-Way Reversible Multi-Head Finite Automata
• Degrees of Reversibility for DFA and DPDA
• Minimal Reversible Deterministic Finite Automata
• One-Way Reversible Multi-head Finite Automata
• Irreversibility and Heat Generation in the Computing Process
• Time/Space Trade-Offs for Reversible Computation
• Inference of Reversible Languages
• The Power of the Queue
• Reversible Queue Automata
• Developments in Language Theory
• Real-Time Reversible One-Way Cellular Automata
• Logical Reversibility of Computation

This page was built for publication: Reversible and Irreversible Computations of Deterministic Finite-State Devices