Computer Science Seminar
Date & Time: 18th January (Wednesday), 10:45 AM to 11:45 AM
Venue: Lecture Hall 804
Equivalence and conjugacy of weighted automata
Jacques Sakarovitch
CNRS, Télécom Paris, France.
18-01-23

---

Abstract

We start from a result in classical finite automata theory: 'Any regular language can be mapped onto any other regular language with the same generating function by a letter-to-letter transducer'.

The model of weighted automata is first introduced to deal with the generating functions of regular languages. We then define the conjugacy of weighted automata, a concept borrowed to symbolic dynamics, and show how the above statement can be derived from the central result of this work: 'Two equivalent weighted automata are conjugate to a third one when the weight semiring is B, N, Z, or any Euclidean domain (and thus any (skew) field)'.

Joint work with Marie-Pierre Béal and Sylvain Lombardy.