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

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

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)

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

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)