Minimizing incomplete automata

Keywords

Automaton, Alphabet, Partition (number theory), Minification, Partition problem

References

• Applied Combinatorics on Words (Encyclopedia of Mathematics and its Applications)M. Lothaire — 2005
• Efficient Translation of External Input in a Dynamically Typed LanguageRobert Paige — 1994
• Algorithms on stringsMaxime Crochemore, Christophe Hancart, Thierry Lecroq — 2007
• Varieties of Formal LanguagesJ. E. Pin — 1986
• Efficient Minimization of DFAs with Partial Transition FunctionsAntti Valmari, Petri Lehtinen — 2008
• An Introduction to Automata TheoryMichael W. Shields — 1988
• The Design and Analysis of Computer AlgorithmsAlfred V. Aho, John E. Hopcroft — 1974
• Minimizing local automataMarie-Pierre Béal, Maxime Crochemore — 2007
• Introduction to Automata Theory, Languages and ComputationJ. Hopcroft, Rajeev Motwani, Rotwani — 1979
• Partitioning a Graph in O(|A| log2 |V|)Alain Cardon, Maxime Crochemore — 1982
• A Linear Time Solution to the Single Function Coarsest Partition ProblemRobert Paige, Robert E. Tarjan, Robert Bonic — 1985
• Describing an algorithm by HopcroftDavid Gries — 1973
• Minimal NFA Problems are HardTao Jiang, Bala Ravikumar — 1991
• Three Partition Refinement AlgorithmsRobert Paige, Robert E. Tarjan — 1987
• Minimisation of Acyclic Deterministic Automata in Linear TimeDominique Revuz — 1992
• Re-describing an algorithm by HopcroftTimo Knuutila — 2001
• An O(n log n) Implementation of the Standard Method for Minimizing n-State Finite AutomataNorbert Blüm — 1996
• Transducers and RepetitionsMaxime Crochemore — 1986
• Eléments d'algorithmiqueDanièle Beauquier, Jean Berstel, Philippe Chrétienne — 1992
• Reducing NFAs by invariant equivalencesLucian Ilie, Sheng Yü — 2003

Cited by

• Induction de requêtes guidée par schémaJérôme Champavère — 2010
• Finite-state Machine Construction Methods and Algorithms for Phonology and MorphologyMichael Hammond, Mans Hulden — 2009
• Bisimulations over DLTS in O(m.log n)-timeGérard Cécé — 2013
• A graph theoretic approach to automata minimalityAntonio Restivo, Roberto Vaglica — 2012
• Fast brief practical DFA minimizationAntti Valmari — 2012
• Average complexity of Moore's and Hopcroft's algorithmsJulien David — 2012
• Average Case Analysis of Moore’s State Minimization AlgorithmFrédérique Bassino, Julien David, Cyril Nicaud — 2011
• Minimization of symbolic automataLoris D’Antoni, Margus Veanes — 2014
• Morphisms and Minimisation of Weighted AutomataSylvain Lombardy, Jacques Sakarovitch — 2021
• Graph Spectral Properties of Deterministic Finite Automata - (Short Paper)Ryoma Sin’ya — 2014
• Minimization of AutomataJean Berstel, Luc Boasson, Olivier Carton — 2010
• [1] Marie-Pierre Béal, Jean Berstel, Soren Eilers, and Dominique Perrin. Symbolic dynamics. CoRR, abs/1006.1265, 2010.Marie-Pierre Béal — 2010
• Alinhamento de sequências restrito por expressão regular usando padrões PROSITELise Rommel Romero Navarrete — 2016
• Morphisms and minimization of weighted automataS. Lombardy, J. Sakarovitch — 2021
• Applications of Symbolic Finite AutomataMargus Veanes — 2013
• Two Routes to Automata Minimization and the Ways to Reach It EfficientlyS. Lombardy, J. Sakarovitch — 2018

Related papers

• Edge-minimization of non-deterministic finite automataBoris Melnikov, Aleksandra Melnikova — 2001
• Simplifying Nondeterministic Finite Cover AutomataCezar Câmpeanu — 2014
• Investigations on Variants of Weighted AutomataI Virgili — 2006
• Controlled finite automataAlexander Meduna, Petr Zemek — 2014
• Behaviour, reduction and minimization of finite :G6-automataKetty Peeva — 1988