article

On Rational Stochastic Languages

Authors:

François Denis,

Yann EspositoAuthors Info & Claims

Fundamenta Informaticae, Volume 86, Issue 1,2

Pages 41 - 77

Published: 01 April 2008 Publication History

Abstract

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 S$^{rat}$$_K$(Σ). 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.

References

[1]

Abe, N., Warmuth, M.: On the computational complexity of approximating distributions by probabilistic automata., Machine Learning, 9, 1992, 205-260.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[3]

Blondel, V. D., Canterini, V.: Undecidable Problems for Probabilistic Automata of Fixed Dimension, Theory of Computing Systems, 36(3), 2003, 231-245.

Crossref

Google Scholar

[4]

Blondel, V. D., Tsitsiklis, J. N.: A Survey of Computational Complexity Results in Systems and Control, Automatica, 36(9), September 2000, 1249-1274.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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.

Google Scholar

[7]

Dempster, A., Laird, N. M., Rubin, D. B.: Maximum likelihood from incomplete data via the EM algorithm., Journal of the Royal Statistical Society, 39, 1977, 1-38.

Google Scholar

[8]

Denis, F., Esposito, Y.: Residual languages and probabilistic automata, 30th International Colloquium, ICALP 2003, number 2719 in LNCS, SV, 2003.

Crossref

Google Scholar

[9]

Denis, F., Esposito, Y.: Learning classes of Probabilistic Automata, COLT 2004, number 3120 in LNAI, 2004.

Crossref

Google Scholar

[10]

Denis, F., Esposito, Y., Habrard, A.: Learning Rational stochastic languages, Proc. of the 19th Annual Conference on Learning Theory, 4005, 2006.

Digital Library

Google Scholar

[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.

Google Scholar

[12]

Denis, F., Lemay, A., Terlutte, A.: Residual Finite State Automata, Fundamenta Informaticae, 51(4), 2002, 339-368.

Digital Library

Google Scholar

[13]

Denis, F., Lemay, A., Terlutte, A.: Learning Regular languages using RFSAs, Theoretical Computer Science, 2(313), 2004, 267-294.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[15]

Eilenberg, S.: Automata, Languages and Machines, vol. A, New York: Academic Press, 1974.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[17]

Fliess, M.: Matrices de Hankel, J. Maths. Pures Appl., 53, 1974, 197-222, + erratum in Vol. 54 (1975).

Google Scholar

[18]

Gantmacher, F. R.: Théorie des matrices, tomes 1 et 2, Dunod, 1966.

Google Scholar

[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.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[21]

Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

Digital Library

Google Scholar

[22]

Jacob, G.: Sur un théorème de Shamir, Information and control, 27, 1975, 218-261.

Google Scholar

[23]

Karp, R. M.: Complexity of Computer Communications, chapter Reducibility among combinatorial problems, Plenum Press, 1972, 85-103.

Google Scholar

[24]

Sakarovitch, J.: Éléments de théorie des automates, Éditions Vuibert, 2003.

Google Scholar

[25]

Salomaa, A., Soittola, M.: Automata: Theoretic Aspects of Formal Power Series, Springer-Verlag, 1978.

Crossref

Google Scholar

[26]

Schützenberger, M. P.: On the definition of a family of automata, Information and Control, 4, 1961, 245-270.

Crossref

Google Scholar

Cited By

View all

Balle BMaillard O(2017)Spectral learning from a single trajectory under finite-state policiesProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305381.3305419(361-370)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.5555/3305381.3305419
Rabusseau GBalle BPineau J(2017)Multitask spectral learning of weighted automataProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3294996.3295019(2585-2594)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.5555/3294996.3295019
Thon MJaeger H(2015)Links between multiplicity automata, observable operator models and predictive state representationsThe Journal of Machine Learning Research10.5555/2789272.278927616:1(103-147)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2789272.2789276
Show More Cited By

Index Terms

On Rational Stochastic Languages
1. Theory of computation

Recommendations

On Rational Stochastic Languages

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 ...
R70-3 On Stochastic Languages

A stochastic language is a set of words accepted by a probabilistic automaton with some cutpoint. The structure of the family of stochastic languages may not parallel the structure of the family of regular languages. Some stochastic languages are context-...
Learning rational stochastic languages
COLT'06: Proceedings of the 19th annual conference on Learning Theory

Given a finite set of words w₁, ..., w_nindependently drawn according to a fixed unknown distribution law P called a stochastic language, a usual goal in Grammatical Inference is to infer an estimate of P in some class of probabilistic models, such as ...

Reviews

Reviewer: Bruce E. Litow

This paper presents a series of interrelated results on classes of formal power series that are generated by various types of weighted finite automata. In the early 1960s, Schützenberger initiated the idea of studying rational languages in terms of matrices over semirings. Several studies in this area, including Kuich and Salomaa's book [1], are, curiously, not cited by the authors. A possible explanation for this is the authors' concentration on and . This paper is a valuable contribution to the linear algebra approach to formal languages. Although the authors' stated goal is to provide a unified account of this field (which is largely achieved) for use in grammatical inference research, there are numerous main results and technical propositions that are useful for other formal language investigations. A distinguishing feature of the exposition is the frequent employment of genuinely illustrative examples. Both its design and content lead me to recommend this paper to a wide range of theorists. The paper contains several tables and summaries that the interested reader can consult directly, so I will not attempt to present them here. It should be noted that the terminology in this field is not entirely standard. For example, weighted finite automata, as defined by Kuich and Salomaa [1], are referred to as multiplicity automata in this paper, with other automata being variants of the classical stochastic automaton, dating back to Rabin and Paz in the 1960s. Several results concerning equivalence/inequivalence are established. Considerable space is devoted to the residual formal series u {-1} ... p of a stochastic formal series p . This is defined by (recall we work over at least u {-1} ... p ( w ) = p ( uw )/ p ( u Σ*), where, as usual, Σ is a finite alphabet. The residual can be thought of as a normalization with regard to u for p in terms of the weight assigned by p to all words u Σ*. The algebraic significance of the residual is brought out in terms of finite generation results. There are also decidability results, both positive and negative, which are in part associated with finite generation. In the same spirit, some PTIME automaton representability algorithms and one PSPACE completeness theorem are given. Fatou results are also presented. Several of these deal with when a series with all of its coefficients in (the positive sub-semiring of ) can be generated by matrices in . Finally, I can't resist mentioning one of the technical results in the paper that undoubtedly will find use in other applications: Lemma 1: Let f : be a linear mapping and let such that converges to u . Then u . Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Fundamenta Informaticae Volume 86, Issue 1,2

October 2008

219 pages

ISSN:0169-2968

Issue’s Table of Contents

Publisher

IOS Press

Netherlands

Publication History

Published: 01 April 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Balle BMaillard O(2017)Spectral learning from a single trajectory under finite-state policiesProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305381.3305419(361-370)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.5555/3305381.3305419
Rabusseau GBalle BPineau J(2017)Multitask spectral learning of weighted automataProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3294996.3295019(2585-2594)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.5555/3294996.3295019
Thon MJaeger H(2015)Links between multiplicity automata, observable operator models and predictive state representationsThe Journal of Machine Learning Research10.5555/2789272.278927616:1(103-147)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2789272.2789276
Glaude HEnderli CPietquin O(2015)Non-negative Spectral Learning for Linear Sequential SystemsProceeings, Part II, of the 22nd International Conference on Neural Information Processing - Volume 949010.1007/978-3-319-26535-3_17(143-151)Online publication date: 9-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-26535-3_17
Bailly RDenis F(2011)Absolute convergence of rational series is semi-decidableInformation and Computation10.1016/j.ic.2010.11.004209:3(280-295)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.ic.2010.11.004
Bailly RHabrard ADenis F(2010)A spectral approach for probabilistic grammatical inference on treesProceedings of the 21st international conference on Algorithmic learning theory10.5555/1893193.1893207(74-88)Online publication date: 6-Oct-2010
https://dl.acm.org/doi/10.5555/1893193.1893207
Bailly RDenis FRalaivola LDanyluk ABottou LLittman M(2009)Grammatical inference as a principal component analysis problemProceedings of the 26th Annual International Conference on Machine Learning10.1145/1553374.1553379(33-40)Online publication date: 14-Jun-2009
https://dl.acm.org/doi/10.1145/1553374.1553379

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations