WeightedWord Recognition

Article type: Research Article

Authors: Laugerotte, Éric | Ziadi, Djelloul

Affiliations: Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes Université de Rouen 76801 Saint Étienne du Rouvray France. E-mails: Eric.Laugerotte@univ-rouen.fr; Djelloul.Ziadi@univ-rouen.fr

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: Star, weighted automata, regular weighted expressions, Thompson automata, elimination, recognizable words

Journal: Fundamenta Informaticae, vol. 83, no. 3, pp. 277-298, 2008