Hopcroft’s Algorithm and Cyclic Automata

DOI10.1007/978-3-540-88282-4_17MaRDI QIDQ3540107zbMATHOpenAlexFDO

Authors M. Sciortino, G. Castiglione, Antonio Restivo

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 wordsminimal automatonHopcroft's algorithm

Mathematics Subject Classification ID

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

Recommendations

• On Extremal Cases of Hopcroft’s Algorithm
• Implementation and Application of Automata
• On extremal cases of Hopcroft's algorithm
• Re-describing an algorithm by Hopcroft
• Circular Sturmian words and Hopcroft's algorithm
• An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
• Hopcroft's algorithm and tree-like automata
• Average complexity of Moore's and Hopcroft's algorithms
• Hopcroft’s Minimization Technique: Queues or Stacks?
• Hopcroft's automaton minimization algorithm and Sturmian words

Cites work

• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 194969 (Why is no real title available?)
• scientific article; zbMATH DE number 3266653 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Around Hopcroft’s Algorithm
• Describing an algorithm by Hopcroft
• Experimental Evaluation of Classical Automata Constructions
• Implementation and Application of Automata
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Minimisation of acyclic deterministic automata in linear time
• On Christoffel classes
• Re-describing an algorithm by Hopcroft

Cited in

(23)

• A combinatorial view on string attractors
• String attractors and infinite words
• On Extremal Cases of Hopcroft’s Algorithm
• Average case analysis of Moore's state minimization algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Standard Sturmian words and automata minimization algorithms
• Lowerbounds for Bisimulation by Partition Refinement
• A challenging family of automata for classical minimization algorithms
• New string attractor-based complexities for infinite words
• Novel results on the number of runs of the Burrows-Wheeler-transform
• Average complexity of Moore's and Hopcroft's algorithms
• Minimisation of automata
• Hyper-minimisation Made Efficient
• Hopcroft's algorithm and tree-like automata
• Implementation and Application of Automata
• On the Hopcroft's minimization technique for DFA and DFCA
• Around Hopcroft’s Algorithm
• Circular Sturmian words and Hopcroft's algorithm
• An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
• On extremal cases of Hopcroft's algorithm
• Hopcroft’s Minimization Technique: Queues or Stacks?
• Re-describing an algorithm by Hopcroft
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton

This page was built for publication: Hopcroft’s Algorithm and Cyclic Automata

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