Noncommutative Rings and applications

Supported by FAPESP (Projeto Tematico 2020/16594-0, coordinated by Cesar Polcino Milies)

Next Seminar

Date: May 12, 2026

Time: 15:00 (São Paulo Time: UCT-3)

Location: IME, Room B-05

Speaker: Jacques Sakarovitch

(IRIF - CNRS/Paris Cité University and LTCI - Télécom Paris, Institut Polytechnique de Paris)

Title: Conjugacy and equivalence of weighted finite automata

Abstract:

We continue with the study of the computation model provided by weighted finite automata.

If equivalence of finite automata is easily decidable, it is not the case anymore for weighted automata in general and decidability of equivalence then depends upon the properties of the semiring of weights. We present two results which lead to a structural interpretation of equivalence for weighted automata.

The first result relates equivalence to conjugacy, a concept borrowed to symbolic dynamics. It states, in the case of a number of weight semirings, that two equivalent automata are conjugate to a third one. It turns out that the effective computation of the latter coincide with the decidability of equivalence of automata.

The second result establishes then, under a 'decomposability' hypothesis on the weight semiring, that a conjugacy can be factorised as a product of a morphism and a co-morphism, the definition of which is also based on conjugacy. Finally, under a supplementary mild 'reconstruction' hypothesis, it then follows that two equivalent automata are essentially the image of a third one under a cascade of morphisms and co-morphisms, showing that there exists a kind of relation between the computations of two equivalent automata.

To give flesh to these results, let us quote a consequence in 'classical' finite automata theory, which can also serve as a teaser for the talk: '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'.

Joint work with Marie-Pierre Béal (LIGM - Univ. Gustave Eiffel) and Sylvain Lombardy (LaBRI, Institut Polytechnique de Bordeaux)