Minimal and Reduced Reversible Automata

DOI10.1007/978-3-319-41114-9_13MaRDI QIDQ2829980zbMATH OpenOpenAlexFDO

Authors Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero

Publication date 9 November 2016

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06840

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: A condition characterizing the class of regular languages which have several nonisomorphic minimal reversible automata is presented. The condition concerns the structure of the minimum automaton accepting the language under consideration. It is also observed that there exist reduced reversible automata which are not minimal, in the sense that all the automata obtained by merging some of their equivalent states are irreversible. Furthermore, a sufficient condition for the existence of infinitely many reduced reversible automata accepting a same language is given. It is also proved that, when the language is accepted by a unique minimal reversible automaton (that does not necessarily coincide with the minimum deterministic automaton), then no other reduced reversible automata accepting it can exist.

Recommendations

• Minimal and reduced reversible automata
• Minimal reversible deterministic finite automata
• Minimal reversible deterministic finite automata
• Concise representations of reversible automata
• Concise representations of reversible automata
• Reversible limited automata
• Reversible limited automata
• Minimisation of automata
• Reversible languages having finitely many reduced automata
• A lower bound for reversible automata

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Aspects of reversibility for classical automata
• Inference of Reversible Languages
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• Minimal reversible deterministic finite automata
• Reversible and irreversible computations of deterministic finite-state devices
• Reversible space equals deterministic space

Cited in

(18)

• scientific article; zbMATH DE number 1870550 (Why is no real title available?)
• Weakly and Strongly Irreversible Regular Languages
• Minimal and reduced reversible automata
• Reversible languages having finitely many reduced automata
• scientific article; zbMATH DE number 3864507 (Why is no real title available?)
• A lower bound for reversible automata
• Primitive and irreducible automata
• scientific article; zbMATH DE number 3903976 (Why is no real title available?)
• On the k-reversibility of finite automata
• scientific article; zbMATH DE number 1962780 (Why is no real title available?)
• Bideterministic automata and minimal representations of regular languages
• scientific article; zbMATH DE number 7444007 (Why is no real title available?)
• On locally reversible languages
• A small minimal aperiodic reversible Turing machine
• scientific article; zbMATH DE number 4020506 (Why is no real title available?)
• Minimal reversible deterministic finite automata
• Minimal reversible deterministic finite automata
• Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata

This page was built for publication: Minimal and Reduced Reversible Automata

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