Equivalence of weighted automata: a survey of 54 years of research
Jacques Sakarovitch
CNRS and Telecom ParisTech, Paris
Joint work with Sylvain Lombardy, Institut Polytechnique de Bordeaux
DEIB - Seminar Room
January 29th, 2016
10.30 am
Contact:
Pierluigi San Pietro
Research Line:
Advanced software architectures and methodologies
CNRS and Telecom ParisTech, Paris
Joint work with Sylvain Lombardy, Institut Polytechnique de Bordeaux
DEIB - Seminar Room
January 29th, 2016
10.30 am
Contact:
Pierluigi San Pietro
Research Line:
Advanced software architectures and methodologies
Abstract
This survey reviews some of the significant results established in the field of weighted automata by taking the problem of equivalence as a leading thread.
It will mention in particular the following points: the properties of the family of languages defined as support of rational series, the decidability of the equivalence of deterministic transducers, the computation of reduced representations for automata with weights taken in a field and its generalisation to an exploration procedure, and the relation between equivalence and conjugacy for certain weight semirings.
It will mention in particular the following points: the properties of the family of languages defined as support of rational series, the decidability of the equivalence of deterministic transducers, the computation of reduced representations for automata with weights taken in a field and its generalisation to an exploration procedure, and the relation between equivalence and conjugacy for certain weight semirings.