6533b874fe1ef96bd12d63f6
RESEARCH PRODUCT
A challenging family of automata for classical minimization algorithms
Marinella SciortinoCyril NicaudGiusi Castiglionesubject
Mathematical optimizationComputer science[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technology01 natural sciencesMeasure (mathematics)Classical Minimization AlgorithmAutomatonRegular languageDFA minimization010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringWorst-case complexity020201 artificial intelligence & image processingMinificationState (computer science)AlgorithmComputer Science::Formal Languages and Automata TheoryComputingMilieux_MISCELLANEOUSdescription
In this paper a particular family of deterministic automata that was built to reach the worst case complexity of Hopcroft's state minimization algorithm is considered. This family is also challenging for the two other classical minimization algorithms: it achieves the worst case for Moore's algorithm, as a consequence of a result by Berstel et al., and is of at least quadratic complexity for Brzozowski's solution, which is our main contribution. It therefore constitutes an interesting family, which can be useful to measure the efficiency of implementations of well-known or new minimization algorithms.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-01-01 |