Centre national de la recherche scientifique
and
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.