We improve some results relative to the state complexity of the multiple catenations described by Gao and Yu. In particular we nearly divide by 2 the size of the alphabet needed for witnesses. We also give some refinements to the algebraic expression of the state complexity, which is especially complex with this operation. We obtain these results by using peculiar DFAs defined by Brzozowski.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.