Weighted Word Recognition

• Autorzy: Laugerotte E. , Ziadi D.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we introduce the notion of Thompson weighted automaton. We show that an e-free automaton constructed from the Thompson weighted automaton for a regular weighted expression E can be computed in quadratic time on the size of E. Moreover the coefficient of a word u in the noncommutative formal series associated to E, can be computed in time O(|u|×|E|).

Słowa kluczowe

EN

star; weighted automata; regular weighted expressions; Thompson automata; elimination; recognizable words

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 3
• Strony: 277--298
• Opis fizyczny: bibliogr. 22 poz., tab., wykr.

Twórcy

autor

Laugerotte E.

autor

Ziadi D.

• Laboratoire d'Informatique, de Traitement de l'Information et des Systems, 76801 Saint Etienne du Rouvray France,

Bibliografia

• [1] Abbad, H., Laugerotte, E.: Symbolic Automata and MuPAD-Combinat, To be submitted.
• [2] Aho, A., Sethi, R., Ullman, J.: Compilers principles, techniques and tools, Addison-Wesley, 1986.
• [3] Berstel, J., Reutenauer, C: Rational series and their languages, Springer-Verlag, 1988.
• [4] Caron, P., Flouret, M.: Glushkov construction for multiplicities, Proc. 5th Int. Conf. on Implementations and Applications of Automata (S. Yu, A. Paun, Eds.), 2088, Springer-Verlag, 2001.
• [5] Champarnaud, J.-M., Laugerotte, E., Ouardi, F., Ziadi, D.: From regular weighted expressions to finite automata, International Journal of Foundation Computer Science, 15, 2004, 687-700.
• [6] Cormen, T. H., Leiserson, C. E., Rivest, R. L.: Introduction to algorithms, MIT Press, 1989.
• [7] Cortes, C, Haffner, P., Mohri, M.: Rational kernels: theory and algorithms, Journal of Machine Learning Research, 5, 2004, 1035-1062.
• [8] Duchamp, G., Flouret, M., Laugerotte, E., Luque, J.-G.: Direct and dual laws for automata with multiplicities, Theoretical Computer Science, 267, 2001,105-120.
• [9] Duchamp, G., Kacem, H. H., Laugerotte, E.: Algebraic elimination of e-transitions, Discrete Mathematics and Theoretical Computer Science, 2005, 51-70.
• [10] Giraud, M., Lavenier, D.: Dealing with hardware space limits when removing epsilon-transitions in a ge-nomic weighted finite automaton, Journal of Automata, Languages and Combinatorics, 10, 2005, 265-285.
• [11] Hebisch, U., Weinert, H. J.: Semirings, World Scientific, 1993.
• [12] Hivert, F., Thiery, N. M.: MuPAD-Combinat, an open-source package for research in algebraic combinatorics, Proc. Seminaire Lotharingien de Combinatoire, 2004.
• [13] Katritzke, F., Merzenich, W., Thomas, M.: Enhancements of partitioning techniques for image compression using weighted finite automata, Theoretical Computer Science, 313, 2004, 133-144.
• [14] Kuich, W., Salomaa, A.: Semirings, automata, languages, Springer-Verlag, 1986.
• [15] Lombardy, S., Sakarovitch, J.: Derivatives of rational expressions with multiplicity, Theoretical Computer Science, 332, 2005, 141-177.
• [16] Majewski, M.: MuPAD Pro computing essentials, Springer-Verlag, 2000
• [17] Mohri, M.: Generic epsilon-removal algorithm for weighted automata, Proc. 5th Int. Conf. on Implementations and Applications of Automata (S. Yu, A. Paun, Eds.), 2088, Springer-Verlag, 2001.
• [18] Mohri, M., Pereira, F. C. N., Riley, M.: The design principles of a weighted finite-state transducer library, Theoretical Computer Science, 231, 2000, 17-32.
• [19] Sakarovitch, J.: Elements de theorie des automates, Vuibert, 2003.
• [20] Schlitzenberger, M. P.: On the definition of a family of automata, Information and Control, 4, 1961,245-270.
• [21] Stanley, R. P.: Enumerative combinatorics, Cambridge University Press, 1999.
• [22] Thompson, K.: Regular expression search algorithms, Communications of the ACM, 11,1968,419-422