Implementation and Application of Automata

DOI10.1007/B105090MaRDI QIDQ5464005zbMATH OpenOpenAlexFDO

Authors Jean Berstel, Olivier Carton

Publication date 17 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b105090

Mathematics Subject Classification ID

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

Recommendations

• Hopcroft’s Algorithm and Cyclic Automata
• On extremal cases of Hopcroft's algorithm
• Average complexity of Moore's and Hopcroft's algorithms
• A challenging family of automata for classical minimization algorithms
• On Extremal Cases of Hopcroft’s Algorithm

Cited in

(26)

• The state complexity of \(L^{2}\) and \(L^k\)
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Deterministic Pushdown Automata and Unary Languages
• A graph theoretic approach to automata minimality
• Circular Sturmian words and Hopcroft's algorithm
• Forward bisimulations for nondeterministic symbolic finite automata
• Lowerbounds for Bisimulation by Partition Refinement
• On the Hopcroft's minimization technique for DFA and DFCA
• Epichristoffel Words and Minimization of Moore Automata
• Minimisation of automata
• On the average complexity of Moore's state minimization algorithm
• Morphisms and Minimisation of Weighted Automata
• Hopcroft’s Algorithm and Cyclic Automata
• Re-describing an algorithm by Hopcroft
• The average complexity of Moore's state minimization algorithm is \(\mathcal O( n \log\log n)\)
• 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
• 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
• On Extremal Cases of Hopcroft’s Algorithm
• Hopcroft’s Minimization Technique: Queues or Stacks?
• scientific article; zbMATH DE number 4119632 (Why is no real title available?)
• Hopcroft's algorithm and tree-like automata

This page was built for publication: Implementation and Application of Automata

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