Finite automata are the simplest model of computing machines. At the cross-road of so many theorems,
Finite automata are the simplest model of computing machines. At the cross-road of so many theorems, they are part of the base of theoretical computer science as well as they appear as building bricks in many piece of software for pattern recognition, formal verification, computational linguistics, etc. It is then easy, and natural, to enrich the model so that a finite automaton is not a machine that accept or reject a sequence of symbols anymore but rather a machine that 'computes' a multiplicity for every sequence of symbols. According to where this value is taken, whether it is an integer, a set of tuple of integers, another sequence of symbols, etc. these 'weighted' automata have the capacity of modelizing as many different kind of processes, from discrete event systems to timed automata to probabilistic speech recognition systems. As always with modelization, the decidability of the equivalence of two machines is a problem that immediately arises. In this talk, I will first sketch briefly the framework of the study of weighted automata. A key result due to Schützenberger (1961) is the decidability of equivalence of automata with multiplicity in a (skew) field, via the computation of reduced representations. It is noteworthy to quote that the long standing equivalence problem of deterministic k-tape automata was eventually solved (Harju & Karhumaki 1988) by reduction to that result. I shall then present a recent result from a joint work with Marie-Pierre Beal and Sylvain Lombardy, where we introduce the notion of conjugacy of automata, a notion borrowed to symbolic dynamic. Two conjugated automata are equivalent and we shall see that conversely, in the cases where equivalence is known to be decidable, two equivalent automata are conjugated to a same third automaton. This will give us the opportunity to revisit classical constructions on automata such as determinization or reduction of representations over a field. If time allows, we shall also see how we have been able to deduce from this result on automata with natural integer weights an answer to an open question in the theory of automatic structures.

Date and Venue

Start Date
Venue
DMP - 0.07

Speaker

Jacques Sakarovitch (CNRS/ENST, Paris)

Area

Semigroups, Automata and Languages