Weighted word recognition
In this paper, we introduce the notion of Thompson weighted automaton. We show that an epsilon-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(vertical bar u vertical bar x vertical bar E vertical bar).
regular weighted expressions star weighted automata thompson automata elimination recognizable words