On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs

DOI10.1007/978-3-642-31606-7_20zbMath1297.68144OpenAlexW1518218681MaRDI QIDQ2914712

Tomáš Masopust, Galina Jirásková

Publication date: 20 September 2012

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31606-7_20

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (3)

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Learning from positive and negative examples: dichotomies and parameterized algorithms ⋮ Synchronization problems in automata without non-trivial cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a structural property in the state complexity of projected regular languages
• Synthesis of controllable and normal sublanguages for discrete-event systems using a coordinator
• On the state complexity of reversals of regular languages
• Characterizations of some classes of regular events
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• Supervisory control synthesis of discrete-event systems using a coordination scheme
• Complexity of some problems from the theory of automata
• On biautomata
• Note on Reversal of Binary Regular Languages

This page was built for publication: On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs