Minimal and Reduced Reversible Automata

DOI10.1007/978-3-319-41114-9_13zbMATH Open1476.68133arXiv1611.06840OpenAlexW2478542454MaRDI QIDQ2829980FDOQ2829980

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)

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.

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• Inference of Reversible Languages
• Reversible and irreversible computations of deterministic finite-state devices
• Minimal reversible deterministic finite automata
• Aspects of reversibility for classical automata
• Reversible space equals deterministic space

Cited In (17)

• On locally reversible languages
• Bideterministic automata and minimal representations of regular languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reversible languages having finitely many reduced automata
• A lower bound for reversible automata
• Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata
• Primitive and irreducible automata
• Title not available (Why is that?)
• A small minimal aperiodic reversible Turing machine
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the k-reversibility of finite automata
• Title not available (Why is that?)
• Minimal reversible deterministic finite automata
• Minimal reversible deterministic finite automata
• Minimal and reduced reversible 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)