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.

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.

AG is a set of packages for manipulating finite state automata and finite semigroups. This software includes on the one hand the AUTOMAP package which affords the usual operations on automata (union, concatenation, Kleene closure,.) as well as the usual transformations (trimming, minimization,.) and on the other hand the GREEN package which yields the (regular or not) D-class structure of a finite monoid. The AG software has been implemented using the Maple symbolic computation system. ©1997 by John Wiley & Sons, Ltd.