Conjugacy and Equivalence of Weighted Automata and Functional Transducers

Marie-Pierre Béal (1) , Sylvain Lombardy (2) , Jacques Sakarovitch (3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
3 LTCI - Laboratoire Traitement et Communication de l'Information

We show that two equivalent K-automata are conjugate to a third one, when K is equal to B, N, Z, or any (skew) ¯eld and that the same holds true for functional tranducers as well.

Domaines: Algorithme et structure de données [cs.DS]

Marie-Pierre Béal, Sylvain Lombardy, Jacques Sakarovitch. Conjugacy and Equivalence of Weighted Automata and Functional Transducers. 1st International Computer Science Symposium in Russia (CSR 2006), Jun 2006, St. Petersburg, Russia. pp.58-69. ⟨hal-00619855⟩