An introduction to the study of weighted automata: on rational languages with equal generating functions

Jacques Sakarovitch

Centre national de la recherche scientifique
Département informatique et réseaux
Télécom ParisTech

Friday, 23 March 2012, 14:00 (note the unusual time!)
Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

Abstract: If two regular languages $L$ and $K$ have the same generating functions, that is, for every integer $n$ they have the same number of words of length $n$, there exists a rational bijection realised by a letter-to-letter transducer that maps $L$ onto $K$.

This statement is a consequence of a refinement of the decidability of the equivalence of two automata with multiplicity in $N$.

It will give us the opportunity to review first the basic definitions and results on weighted finite automata, and how they generalize the corresponding properties of classical finite automata.

Tarmo Uustalu
Last update 9.4.2012