Duchamp, Gérard H. E.; Kacem, Hatem Hadj; Laugerotte, Éric Algebraic elimination of \(\epsilon\)-transitions. (English) Zbl 1152.68458 Discrete Math. Theor. Comput. Sci. 7, No. 1, 51-69 (2005). Summary: We here describe a method of removing the \(\epsilon\)-transitions of a weighted automaton. The existence of a solution for this removal depends on the existence of the star of a single matrix which, in turn, is based on the computation of the stars of scalars in the ground semiring. We discuss two aspects of the star problem (by infinite sums and by equations) and give an algorithm to suppress the \(\epsilon\)-transitions and preserve the behaviour. Running complexities are computed. MSC: 68Q45 Formal languages and automata 68Q70 Algebraic theory of languages and automata PDFBibTeX XMLCite \textit{G. H. E. Duchamp} et al., Discrete Math. Theor. Comput. Sci. 7, No. 1, 51--69 (2005; Zbl 1152.68458) Full Text: EuDML Link