Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Wydawca
Czasopismo
Rocznik
Tom
Strony
1--25
Opis fizyczny
Bibliogr. 17 poz., tab., wykr.
Twórcy
autor
autor
- LITIS, Université de Rouen, 76801 Saint Étienne du Rouvray, France, Pascal.Caron@univ-rouen.fr
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0018-0035