On Rational Stochastic Languages

• Autorzy: Denis F. , Esposito Y.
• Języki publikacji: EN

Abstrakty

EN

The goal of the present paper is to provide a study of rational stochastic languages over a semiring KÎ{ Q, R, Q+, R+}. A rational stochastic language is a probability distribution over a free monoid ?*, which is rational over K, that is, which can be generated by a multiplicity automaton with parameters in K. We study the relations between the classes of rational stochastic languages SKrat(σ). We define the notion of residual language of a stochastic language and we use it to investigate properties of several subclasses of rational stochastic languages. Then, we study the representation of rational stochastic languages by means of multiplicity automata. Lastly, we show some connections between properties of rational stochastic languages and results obtained in the field of probabilistic grammatical inference.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 86, nr 1-2
• Strony: 41--77
• Opis fizyczny: bibliogr. 26 poz., wykr.

Twórcy

autor

Denis F.

autor

Esposito Y.

• LIF-CMI, 39 rue F.Joliot Curie, 13013 Marseille, France,

Bibliografia

• [1] Abe, N., Warmuth, M.: On the computational complexity of approximating distributions by probabilistic automata., Machine Learning, 9, 1992, 205-260.
• [2] Berstel, J., Reutenauer, C.: Rational series and their languages, Springer-Verlag New York, Inc., New York, NY, USA, 1988, ISBN 0-387-18626-3.
• [3] Blondel, V. D., Canterini, V.: Undecidable Problems for Probabilistic Automata of Fixed Dimension, Theory of Computing Systems, 36(3), 2003, 231-245.
• [4] Blondel, V. D., Tsitsiklis, J. N.: A Survey of Computational Complexity Results in Systems and Control, Automatica, 36(9), September 2000, 1249-1274.
• [5] Carrasco, R. C., Oncina, J.: Learning Stochastic Regular Grammars by Means of a State Merging Method, ICGI (R. C. Carrasco, J. Oncina, Eds.), 862, Springer, 1994, ISBN 3-540-58473-0.
• [6] Carrasco, R. C., Oncina, J.: Learning deterministic regular grammars from stochastic samples in polynomial time, RAIRO (Theoretical Informatics and Applications), 33(1), 1999, 1-20.
• [7] Dempster, A., Laird, N. M., Rubin, D. B.: Maximum likelihood from incomplete data via the EMalgorithm., Journal of the Royal Statistical Society, 39, 1977, 1-38.
• [8] Denis, F., Esposito, Y.: Residual languages and probabilistic automata, 30th International Colloquium, ICALP 2003, number 2719 in LNCS, SV, 2003.
• [9] Denis, F., Esposito, Y.: Learning classes of Probabilistic Automata, COLT 2004, number 3120 in LNAI, 2004.
• [10] Denis, F., Esposito, Y., Habrard, A.: Learning Rational stochastic languages, Proc. of the 19th Annual Conference on Learning Theory, 4005, 2006.
• [11] Denis, F., Habrard, A.: Learning Rational Stochastic Tree Languages, ALT (M. Hutter, R. A. Servedio, E. Takimoto, Eds.), 4754, Springer, 2007, ISBN 978-3-540-75224-0.
• [12] Denis, F., Lemay, A., Terlutte, A.: Residual Finite State Automata, Fundamenta Informaticae, 51(4), 2002, 339-368.
• [13] Denis, F., Lemay, A., Terlutte, A.: Learning Regular languages using RFSAs, Theoretical Computer Science, 2(313), 2004, 267-294.
• [14] Dupont, P., Denis, F., Esposito, Y.: Links between Probabilistic Automata and Hidden Markov Models: probability distributions, learning models and induction algorithms, Pattern Recognition: Special Issue on Grammatical Inference Techniques & Applications, 38/9, 2005, 1349-1371.
• [15] Eilenberg, S.: Automata, Languages and Machines, vol. A, New York: Academic Press, 1974.
• [16] Esposito, Y., Lemay, A., Denis, F., Dupont, P.: Learning Probabilistic Residual Finite State Automata, ICGI (P. W. Adriaans, H. Fernau, M. van Zaanen, Eds.), 2484, Springer, 2002, ISBN 3-540-44239-1.
• [17] Fliess, M.: Matrices de Hankel, J. Maths. Pures Appl., 53, 1974, 197-222, + erratum in Vol. 54 (1975).
• [18] Gantmacher, F. R.: Th'eorie des matrices, tomes 1 et 2, Dunod, 1966.
• [19] Habrard, A., Denis, F., Esposito, Y.: Using Pseudo-stochastic Rational Languages in Probabilistic Grammatical Inference, ICGI (Y. Sakakibara, S. Kobayashi, K. Sato, T. Nishino, E. Tomita, Eds.), 4201, Springer, 2006, ISBN 3-540-45264-8.
• [20] de la Higuera, C., Thollard, F.: Identification in the Limit with Probability One of Stochastic Deterministic Finite Automata, ICGI (A. L. Oliveira, Ed.), 1891, Springer, 2000, ISBN 3-540-41011-2.
• [21] Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
• [22] Jacob, G.: Sur un th'eor`eme de Shamir, Information and control, 27, 1975, 218-261.
• [23] Karp, R.M.: Complexity of Computer Communications, chapter Reducibility among combinatorial problems, Plenum Press, 1972, 85-103.
• [24] Sakarovitch, J.: 'El'ements de th'eorie des automates, 'Editions Vuibert, 2003.
• [25] Salomaa, A., Soittola, M.: Automata: Theoretic Aspects of Formal Power Series, Springer-Verlag, 1978.
• [26] Schützenberger,M. P.: On the definition of a family of automata, Information and Control, 4, 1961, 245-270.