eng
episciences.org
Fundamenta Informaticae
0169-2968
1875-8681
2022-10-21
Volume 186, Issues 1-4:...
10.46298/fi-2022-8870
8870
journal article
Morphisms and minimisation of weighted automata
Sylvain Lombardy
Jacques Sakarovitch
This paper studies the algorithms for the minimisation of weighted automata.
It starts with the definition of morphisms-which generalises and unifies the
notion of bisimulation to the whole class of weighted automata-and the unicity
of a minimal quotient for every automaton, obtained by partition refinement.
From a general scheme for the refinement of partitions, two strategies are
considered for the computation of the minimal quotient: the Domain Split and
the Predecesor Class Split algorithms. They correspond respectivly to the
classical Moore and Hopcroft algorithms for the computation of the minimal
quotient of deterministic Boolean automata. We show that these two strategies
yield algorithms with the same quadratic complexity and we study the cases when
the second one can be improved in order to achieve a complexity similar to the
one of Hopcroft algorithm.
https://fi.episciences.org/8870/pdf
Computer Science - Discrete Mathematics
Computer Science - Formal Languages and Automata Theory