Minimal reversible deterministic finite automata

DOI10.1142/S0129054118400063zbMATH Open1387.68156OpenAlexW2796797028MaRDI QIDQ4640040FDOQ4640040

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

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

zbMATH Keywords

decidabilitydescriptional complexityminimalitystructural characterizationNL-completenessreversible finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Space-bounded hierarchies and probabilistic computations
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• Nondeterministic Space is Closed under Complementation
• Inference of Reversible Languages
• The method of forced enumeration for nondeterministic automata
• A simple and efficient universal reversible Turing machine
• One-way reversible multi-head finite automata
• Reversible pushdown automata
• Learning approximately regular languages with reversible languages
• Title not available (Why is that?)
• Two-way reversible multi-head finite automata
• The parallel complexity of finite-state automata problems
• Aspects of reversibility for classical automata
• A lower bound for reversible automata
• On the efficient construction of quasi-reversible automata for reversible languages
• A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads
• Reversible multi-head finite automata characterize reversible logarithmic space
• Minimal and hyper-minimal biautomata (extended abstract)

Cited In (20)

• 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
• Transducing reversibly with finite state machines
• Reversible Two-Party Computations
• Title not available (Why is that?)
• A small minimal aperiodic reversible Turing machine
• 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
• Minimal and reduced reversible 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)