A Challenging Family of Automata for Classical Minimization Algorithms
From MaRDI portal
Publication:3073644
DOI10.1007/978-3-642-18098-9_27zbMath1297.68112MaRDI QIDQ3073644
Marinella Sciortino, Giuseppa Castiglione, Cyril Nicaud
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
68Q45: Formal languages and automata
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Nondeterministic Moore Automata and Brzozowski’s Algorithm, Nondeterministic Moore automata and Brzozowski's minimization algorithm, Standard Sturmian words and automata minimization algorithms
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