A challenging family of automata for classical minimization algorithms

DOI10.1007/978-3-642-18098-9_27MaRDI QIDQ3073644zbMATH OpenOpenAlexFDO

Authors Cyril Nicaud, M. Sciortino, G. Castiglione

Publication date 11 February 2011

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-18098-9_27

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On extremal cases of Hopcroft's algorithm
• On Extremal Cases of Hopcroft’s Algorithm
• Implementation and Application of Automata
• Minimisation of automata
• Hopcroft’s Algorithm and Cyclic Automata

Cites work

• Building the minimal automaton of \(A ^{*} X\) in linear time, when \(X\) is of bounded cardinality
• Circular Sturmian words and Hopcroft's algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Enumeration and generation with a string automata representation
• Experimental Evaluation of Classical Automata Constructions
• Minimisation of acyclic deterministic automata in linear time
• On extremal cases of Hopcroft's algorithm
• On the average complexity of Moore's state minimization algorithm
• Some combinatorial properties of Sturmian words
• Sturmian trees

Cited in

(6)

• Standard Sturmian words and automata minimization algorithms
• Minimisation of automata
• Implementation and Application of Automata
• Two routes to automata minimization and the ways to reach it efficiently
• Nondeterministic Moore automata and Brzozowski's minimization algorithm
• Nondeterministic Moore automata and Brzozowski's algorithm

This page was built for publication: A challenging family of automata for classical minimization algorithms

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