IMDEA Software

IMDEA initiative

Home > Events > Invited Talks > 2024 > Conjugacy and equivalence of weighted automata

Jacques Sakarovitch

Friday, October 11, 2024

11:00am 302-Mountain View and Zoom3 (https://zoom.us/j/3911012202, password:@s3)

Jacques Sakarovitch, Emeritus Reasearcher and Emeritus Professor, CNRS and Telecom Paris

Conjugacy and equivalence of weighted automata

Abstract:

This talk starts with a result in classical Finite Automata Theory: Two regular languages with the same number of words for each length can be mapped one onto the other by a letter-to-letter (finite) transducer. The notion of generating function of regular languages leads to the in- troduction of the model of weighted automata. The conjugacy of weighted automata, a concept borrowed to symbolic dynamics, is then defined and it is shown 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). This talk is based on a joint work with Marie-Pierre Béal and Sylvain Lom- bardy.