A graph theoretic approach to automata minimality

DOI10.1016/J.TCS.2011.12.049MaRDI QIDQ418805zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Extremal minimality conditions on automata
• Automata with Extremal Minimality Conditions
• Some remarks on automata minimality
• scientific article; zbMATH DE number 2040922
• On the Construction of a Family of Automata That Are Generically Non-minimal

Cites work

• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 2081054 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• scientific article; zbMATH DE number 3328165 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Automata with Extremal Minimality Conditions
• Automata with finite congruence lattices
• Circular Sturmian words and Hopcroft's algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Description and analysis of a bottom-up DFA minimization algorithm
• Implementation and Application of Automata
• Never minimal automata and the rainbow bipartite subgraph problem
• On extremal cases of Hopcroft's algorithm
• On the Hopcroft's minimization technique for DFA and DFCA
• On the average complexity of Moore's state minimization algorithm
• Re-describing an algorithm by Hopcroft
• Some remarks on automata minimality
• The average complexity of Moore's state minimization algorithm is \(\mathcal O( n \log\log n)\)

Cited in

(12)

• Primitivity, uniform minimality, and state complexity of Boolean operations
• scientific article; zbMATH DE number 4081587 (Why is no real title available?)
• Extremal minimality conditions on automata
• ACCEPTABLE STRINGS IN AN AUTOMATON
• Binary and circular automata having maximal state complexity for the set of synchronizing words
• Some remarks on automata minimality
• Never minimal automata and the rainbow bipartite subgraph problem
• Edge-minimization of non-deterministic finite automata
• Automata with Extremal Minimality Conditions
• Interaction graphs of isomorphic automata networks. I: Complete digraph and minimum in-degree
• scientific article; zbMATH DE number 6917169 (Why is no real title available?)
• scientific article; zbMATH DE number 7199591 (Why is no real title available?)

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

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