WeightedWord Recognition
Éric Laugerotte, Djelloul Ziadi · Fundamenta Informaticae · 2008
In this paper, we introduce the notion of Thompson weighted automaton. We show that an ε-free automaton constructed from the Thompson weighted automaton for a regular weighted expression E can be computed in quadratic time on the size of E. Moreover the coefficient of a word u in the noncommutative formal series associated to E, can be computed in time O(∣u∣ × �E∣).