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

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.

Tarmo Uustalu

Last update 9.4.2012