A Challenging Family of Automata for Classical Minimization Algorithms

DOI10.1007/978-3-642-18098-9_27zbMath1297.68112OpenAlexW1867432232MaRDI QIDQ3073644

Marinella Sciortino, Cyril Nicaud, Giuseppa 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)

Related Items (3)

Nondeterministic Moore automata and Brzozowski's minimization algorithm ⋮ Standard Sturmian words and automata minimization algorithms ⋮ Nondeterministic Moore Automata and Brzozowski’s Algorithm

Cites Work

• Unnamed Item
• Circular Sturmian words and Hopcroft's algorithm
• Sturmian trees
• Minimisation of acyclic deterministic automata in linear time
• Some combinatorial properties of Sturmian words
• On extremal cases of Hopcroft's algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Enumeration and generation with a string automata representation
• Building the Minimal Automaton of A * X in Linear Time, When X Is of Bounded Cardinality
• Experimental Evaluation of Classical Automata Constructions

This page was built for publication: A Challenging Family of Automata for Classical Minimization Algorithms