Minimal Reversible Deterministic Finite Automata

DOI10.1142/S0129054118400063zbMath1387.68156OpenAlexW2796797028MaRDI QIDQ4640040

Martin Kutrib, Markus Holzer, Sebastian Jakobi

Publication date: 15 May 2018

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

Full work available at URL: https://doi.org/10.1142/s0129054118400063

zbMATH Keywords

structural characterizationminimalitydecidabilitydescriptional complexityNL-completenessreversible finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (10)

Reversible top-down syntax analysis ⋮ Quotients and atoms of reversible languages ⋮ Unnamed Item ⋮ Weakly and Strongly Irreversible Regular Languages ⋮ Reversible Top-Down Syntax Analysis ⋮ Reversible Two-Party Computations ⋮ Unnamed Item ⋮ Finite automata with undirected state graphs ⋮ Reversible pushdown transducers ⋮ Transducing reversibly with finite state machines

Cites Work

• Unnamed Item
• Unnamed Item
• On the efficient construction of quasi-reversible automata for reversible languages
• Space-bounded hierarchies and probabilistic computations
• The method of forced enumeration for nondeterministic automata
• The parallel complexity of finite-state automata problems
• Learning approximately regular languages with reversible languages
• A Lower Bound For Reversible Automata
• Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
• Aspects of Reversibility for Classical Automata
• A Simple and Efficient Universal Reversible Turing Machine
• Two-Way Reversible Multi-Head Finite 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 Pushdown Automata
• Irreversibility and Heat Generation in the Computing Process
• Nondeterministic Space is Closed under Complementation
• Inference of Reversible Languages
• Logical Reversibility of Computation
• Minimal and Hyper-Minimal Biautomata

This page was built for publication: Minimal Reversible Deterministic Finite Automata