Hopcroft’s Algorithm and Cyclic Automata

DOI10.1007/978-3-540-88282-4_17zbMath1163.68021MaRDI QIDQ3540107

Antonio Restivo, Marinella Sciortino, Giuseppa Castiglione

Publication date: 20 November 2008

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-88282-4_17

zbMATH Keywords

circular words; minimal automaton; Hopcroft's algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

Circular Sturmian words and Hopcroft's algorithm, Average complexity of Moore's and Hopcroft's algorithms, An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton, On extremal cases of Hopcroft's algorithm, Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm, Average case analysis of Moore's state minimization algorithm, Hopcroft's algorithm and tree-like automata, Hyper-minimisation Made Efficient, An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton, On Extremal Cases of Hopcroft’s Algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimisation of acyclic deterministic automata in linear time
• Re-describing an algorithm by Hopcroft
• Describing an algorithm by Hopcroft
• On Christoffel classes
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Experimental Evaluation of Classical Automata Constructions
• Implementation and Application of Automata
• Around Hopcroft’s Algorithm