Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2011

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Glushkov construction for multiplicities

Sortuj według:

Ogranicz wyniki do:

From Glushkov WFAs to K-Expressions

Caron P., Flouret M.

Fundamenta Informaticae

2011

Vol. 109, nr 1

1-25

We take an active interest in the problem of conversion of a Weighted Finite Automaton (WFA) into a 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 K-expression is in the Star Normal Form (SNF) defined by Br¨uggemann-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 K-expression from a GlushkovWFA. A characterization of GlushkovWFAs which are not in SNF is given. This characterization allows us to emphasize a normal form for K-expressions. As for SNF in the boolean case, we show that every K-expression has an equivalent one in normal form having the same Glushkov WFA. We end with an algorithm giving a small normal form K-expression from a GlushkovWFA.