Abstract
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∣).
Keywords
Get full access to this article
View all access options for this article.