Efficient weighted expressions conversion
Weighted automata are efficient data structures for manipulating regular series. They are used in a lot of practical and theoretical applications such as computer algebra, image encoding, speech recognition or text processing. Regular series are also encoded by regular weighted expressions. The equivalence between these two representations, weighted regular expressions and finite automata has been proved in 1961 by Schutzenberger [16]. For the conversion of weighted regular expressions into weighted automata there are principally three algorithms. The first one is due to Caron and Flouret [4]. Their algorithm works recursively on a subset of weighted regular expressions and produces the position automaton. Champarnaud et al. [7] have given an efficient algorithm that converts a weighted regular expression into its position automaton in quadratic time w.r.t. the size of the expression. Their algorithm is mainly based on the use of the KZPC-structure for weighted expressions. The position automaton is a particular one (see [5]) that can have a quadratic number of transitions and (n + 1) states where n is the alphabetic width of the expression. The algorithm of Lombardy and Sakarovitch [14] constructs a weighted automaton that turns out to be the generalization of Antimirov automaton for the Boolean case. The Antimirov automaton [1] has
formal languages and automata complexity of computation