From Glushkov WFAs to K-Expressions

• Autorzy: Caron P. , Flouret M.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Glushkov construction for multiplicities; algorithm of McNaughton-Yamada; normal form for proper K-expressions; border-free proper K-expressions; Glushkov K-graphs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 109, nr 1
• Strony: 1--25
• Opis fizyczny: Bibliogr. 17 poz., tab., wykr.

Twórcy

autor

Caron P.

autor

Flouret M.

• LITIS, Université de Rouen, 76801 Saint Étienne du Rouvray, France,

Bibliografia

• [1] V. Antimirov. Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci., 155:291-319, 1996.
• [2] J. Berstel and C. Reutenauer. Rational series and their languages. EATCSMonographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1988.
• [3] A. Brüggemann-Klein. Regular expressions into finite automata. Theoret. Comput. Sci., 120(2):197- 213, 1993.
• [4] A. Buchsbaum, R. Giancarlo, and J. Westbrook. On the determinization of weighted finite automata. SIAM J. Comput., 30(5):1502-1531, 2000.
• [5] P. Caron and M. Flouret. Glushkov construction for series: the non commutative case. Internat. J. Comput. Math., 80(4):457-472, 2003.
• [6] P. Caron and M. Flouret. Algorithms for Glushkov K-graphs. CoRR, abs/0907.4296v1, 2009.
• [7] P. Caron and M. Flouret. On glushkov K-graphs. In Scientific Applications of Language Methods, volume 2, pages 103-132.World Scientific, 2010.
• [8] P. Caron and D. Ziadi. Characterization of Glushkov automata. Theoret. Comput. Sci., 233(1-2):75-90, 2000.
• [9] S. Eilenberg. Automata, languages and machines, volume A. Academic Press, New York, 1974.
• [10] V.M. Glushkov. On a synthesis algorithmfor abstract automata. Ukr. Matem. Zhurnal, 12(2):147-156, 1960. In Russian.
• [11] K. Culik II and J. Kari. Digital images and formal languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, pages 599-616. svb, 1997.
• [12] S. Lombardy and J. Sakarovitch. Derivatives of rational expressions with multiplicity. Theor. Comput. Sci., 332(1-3):141-177, 2005.
• [13] R. F. McNaughton and H. Yamada. Regular expressions and state graphs for automata. IEEE Transactions on Electronic Computers, 9:39-57,March 1960.
• [14] M.Mohri. Finite-state transducers in language and speech processing. Computat. Ling., 23.2:269-311, 1997.
• [15] F. Pereira and M. Riley. Speech recognition by composition of weighted finite automata. In E. Roche and Y. Schabes, editors, Finite state language processing, pages 431-453, Cambridge, Massachusetts, 1997.M.I.T. Press.
• [16] J. Sakarovitch. Éléments de théorie des automates. Vuibert, Paris, 2003.
• [17] M. P. Schützenberger. On the definition of a family of automata. Inform. and Control, 4:245-270, 1961.