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.
|