Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

State Complexity of Multiple Catenations

Caron P., Luque J.-G., Patrou B.

Fundamenta Informaticae

2018

Vol. 160, nr 3

255--279

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.

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.