Hopcroft’s Algorithm and Cyclic Automata

DOI10.1007/978-3-540-88282-4_17MaRDI QIDQ3540107zbMATH OpenOpenAlexFDO

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)

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

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)