Minimal reversible deterministic finite automata

DOI10.1142/S0129054118400063MaRDI QIDQ4640040zbMATH OpenOpenAlexFDO

Authors Markus Holzer, Sebastian Jakobi, Martin Kutrib

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

decidabilitydescriptional complexityminimalitystructural characterizationNL-completenessreversible finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Minimal reversible deterministic finite automata
• The degree of irreversibility in deterministic finite automata
• Minimal and Reduced Reversible Automata
• Reversible nondeterministic finite automata
• Minimal and reduced reversible automata

Cites work

• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 2086620 (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 simple and efficient universal reversible Turing machine
• Aspects of reversibility for classical automata
• Inference of Reversible Languages
• Irreversibility and Heat Generation in the Computing Process
• Learning approximately regular languages with reversible languages
• Logical Reversibility of Computation
• Minimal and hyper-minimal biautomata (extended abstract)
• Nondeterministic Space is Closed under Complementation
• On the efficient construction of quasi-reversible automata for reversible languages
• One-way reversible multi-head finite automata
• Reversible multi-head finite automata characterize reversible logarithmic space
• Reversible pushdown automata
• Space-bounded hierarchies and probabilistic computations
• The method of forced enumeration for nondeterministic automata
• The parallel complexity of finite-state automata problems
• Two-way reversible multi-head finite automata

Cited in

(20)

• Minimal and reduced reversible automata
• Reversible top-down syntax analysis
• Minimal and Reduced Reversible Automata
• Forbidden patterns for ordered automata
• Reversible Top-Down Syntax Analysis
• Quotients and atoms of reversible languages
• The degree of irreversibility in deterministic finite automata
• Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata
• A small minimal aperiodic reversible Turing machine
• Transducing reversibly with finite state machines
• scientific article; zbMATH DE number 3907771 (Why is no real title available?)
• Reversible Two-Party Computations
• Finite automata with undirected state graphs
• Weakly and Strongly Irreversible Regular Languages
• Reversible computations of one-way counter automata
• The degree of irreversibility in deterministic finite automata
• Reversible pushdown transducers
• Reversible nondeterministic finite automata
• Decision problems for reversible and permutation automata
• Minimal reversible deterministic finite automata

This page was built for publication: Minimal reversible deterministic finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640040)