A graph theoretic approach to automata minimality

DOI10.1016/J.TCS.2011.12.049zbMATH Open1238.68080OpenAlexW1988896922MaRDI QIDQ418805FDOQ418805

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the average complexity of Moore's state 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
• Automata with Extremal Minimality Conditions
• The average complexity of Moore's state minimization algorithm is \(\mathcal O( n \log\log n)\)
• Title not available (Why is that?)
• Some remarks on automata minimality
• Never minimal automata and the rainbow bipartite subgraph problem
• Automata with finite congruence lattices
• Implementation and Application of Automata
• Title not available (Why is that?)
• Circular Sturmian words and Hopcroft's algorithm
• Description and analysis of a bottom-up DFA minimization algorithm

Cited In (12)

• Primitivity, uniform minimality, and state complexity of Boolean operations
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

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)