A graph theoretic approach to automata minimality

DOI10.1016/j.tcs.2011.12.049zbMath1238.68080OpenAlexW1988896922MaRDI QIDQ418805

Antonio Restivo, Roberto Vaglica

Publication date: 30 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.049

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ Extremal minimality conditions on automata ⋮ Primitivity, uniform minimality, and state complexity of Boolean operations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Circular Sturmian words and Hopcroft's algorithm
• Description and analysis of a bottom-up DFA minimization algorithm
• On the Hopcroft's minimization technique for DFA and DFCA
• Re-describing an algorithm by Hopcroft
• On extremal cases of Hopcroft's algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Automata with Extremal Minimality Conditions
• The Average Complexity of Moore’s State Minimization Algorithm Is O( n loglogn)
• Some Remarks on Automata Minimality
• Never Minimal Automata and the Rainbow Bipartite Subgraph Problem
• Implementation and Application of Automata

This page was built for publication: A graph theoretic approach to automata minimality