On the weighted closure problem
- LecturerProf. Jacques Sakarovitch (Ecole nationale supérieure des télécommunications)
Host: Bow-Yaw Wang - Time2012-11-01 (Thu.) 10:30 ~ 12:00
- LocationAuditorium 101 at new IIS Building
Abstract
In this talk, we address the problem of ε-transition removal in weighted automata, which was raised in particular by the writing of the modules for Q- and R-automata in the Vaucanson platform.
From an elementary, always solvable and well-treated, question in the Boolean case, the same problem becomes in the most general case one that may have no solution. Almost all earlier works on weighted automata rule out automata in which such removal leads to infinite summation.
We give here a framework that is rigorous enough for the computation and decision algorithms be well-founded, but large enough to encompass all the ‘natural’cases of weighted automata. The setting of this framework has lead to a new characterisation of the conditions under which the behaviour of a weighted automaton is, or should be considered as, defined.
Joint work by Sylvain Lombardy and Jacques Sakarovitch