中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

On the weighted closure problem

:::

On the weighted closure problem

  • 講者Jacques Sakarovitch 教授 (Ecole nationale supérieure des télécommunications)
    邀請人:王柏堯
  • 時間2012-11-01 (Thu.) 10:30 ~ 12:00
  • 地點資訊所新館101演講廳
摘要

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