Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Two Routes to Automata Minimization and the Ways to Reach It Efficiently
verfasst von : Sylvain Lombardy, Jacques Sakarovitch
Erschienen in: Implementation and Application of Automata
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
This paper reports on the work done for the implementation of the algorithms for the computation of the minimal quotient of an automaton in the Awali platform. In the case of non-deterministic or of weighted automata, the minimal quotient of an automaton is obtained by merging all states in bisimulation. Two strategies are explored for the computation of the coarsest bisimulation equivalence. The first one is an extension of the Moore algorithm for the computation of the minimal quotient of a DFA; the second one is inspired by the Hopcroft algorithm for the same problem. These two strategies yield algorithms with the same quadratic complexity and we study the cases where the second strategy can be improved in order to achieve a complexity similar to the one of Hopcroft algorithm.