From Glushkov WFAs to \mathbb{K}-Expressions

Article type: Research Article

Authors: Caron, Pascal | Flouret, Marianne

Affiliations: LITIS, Université de Rouen, 76801 Saint Étienne du Rouvray, France. [email protected] | LITIS, Université du Havre, 76058 Le Havre Cedex, France. [email protected]

Note: [] Address for correspondence: LITIS, Université de Rouen, 76801 Saint Étienne du Rouvray, France

Abstract: We take an active interest in the problem of conversion of a Weighted Finite Automaton (WFA) into a \mathbb{K}-expression. The known algorithms give an exponential size expression in the number of states of the given automaton. We study the McNaughton-Yamada algorithm in the case of multiplicities and then we show that the resulting \mathbb{K}-expression is in the Star Normal Form (SNF) defined by Brüggemann-Klein [3]. The Glushkov algorithm computes an (n + 1)-state automaton from an expression having n occurrences of letters even in the multiplicity case [5]. We reverse this procedure and get a linear size \mathbb{K}-expression from a Glushkov WFA. A characterization of Glushkov WFAs which are not in SNF is given. This characterization allows us to emphasize a normal form for \mathbb{K}-expressions. As for SNF in the boolean case, we show that every \mathbb{K}-expression has an equivalent one in normal form having the same Glushkov WFA. We end with an algorithm giving a small normal form \mathbb{K}-expression from a Glushkov WFA.

DOI: 10.3233/FI-2011-427

Journal: Fundamenta Informaticae, vol. 109, no. 1, pp. 1-25, 2011