Stochastic Semantics

• Autorzy: Bozapalidis S. , Rahonis G.

Identyfikatory

DOI

10.3233/FI-2017-1463

• Języki publikacji: EN

Abstrakty

EN

We consider stochastic systems of equations of tree series, i.e., systems of equations whose right-hand sides are stochastic tree polynomials. We obtain their least solutions in arbitrary substochastic algebras, using both the [IO]- and OI-substitution mode. In the term algebra, we show that the consistency problem of the least [IO]- and OI-solutions is decidable, by reducing it to the consistency problem of stochastic context-free grammars. We prove a Kleene type theorem for the components of the least OI-solutions. The folklore Mezei-Wright result stating the coincidence of the components of least OI-solutions and behaviors of tree automata fails in the stochastic setup. As an application of our theory, we prove a Kleene theorem for the class of series generated by stochastic context-free grammars.

Słowa kluczowe

EN

stochastic algebras; systems of stochastic trees series; stochastic context-free grammars

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 150, nr 2
• Strony: 143--177
• Opis fizyczny: Bibliogr. 37 poz., rys.

Twórcy

autor

Bozapalidis S.

• Department of Mathematics, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece

autor

Rahonis G.

• Department of Mathematics, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece

Bibliografia

• [1] Esparza J, Gaizer A, Kiefer S. Computing least fixed points of probabilistic systems of polynomials. In: Symposium on Theoretical Aspects of Computer Science 2010 (Nancy, France). 2010 pp. 359-370. URL http://www.stacs-conf.org.
• [2] Etessami K, Stewart A, Yannakakis M. Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars. In: Proceedings of STOC 2012. 2012 pp. 579-588. doi: 10.1145/2213977.2214030.
• [3] Etessami K, Yannakakis M. Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM, 2009; 56 ( 1): 1 —66. doi: 10.1145/1462153.1462154.
• [4] Etessami K, Yannakakis M. Model checking of recursive probabilistic systems. ACM Trans. Comput. Logic, 2012; 13 (2): 1-40. doi: 10.1145/2159531.2159534.
• [5] Mezei J, Wright JB. Algebraic automata and context-free sets. Inform. Control, 1967; 11 (l-2): 3—29. doi: 10.1016/S0019-9958(67)90353-1.
• [6] Bozapalidis S, Fülöp Z, Rahonis G. Equational tree transformations. Theoret. Comput. Sci., 2011; 412: 3676-3692. doi: 10.1016/j.tcs.2011.03.028.
• [7] Berstel J, Reutenauer C. Recognizable formal power series on trees. Theoret. Comput. Sci., 1982; 18: 115-148. doi: 10.1016/0304-3975(82)90019-6.
• [8] Bozapalidis S. Equational elements in additive algebras. Theory of Comput. Syst., 1999; 32: 1-33. doi: 10.1007/s002240000110.
• [9] Bozapalidis S, Fülöp Z, Rahonis G. Equational weighted tree transformations. Acta Inform., 2012; 49: 29-52. doi: 10.1007/s00236-011-0148-5.
• [10] Fülöp Z, Rahonis G. Equational weighted tree transformations with discounting. In: Algebraic Foundations in Computer Science, LNCS 7020. 2011 pp. 112-145. doi: 10.1007/978-3-642-24897-9.
• [11] Ellis CA. Probabilistic tree automata. Inform, and Control, 1971; 19 (5): 401-416. doi: 10.1016/S0019-9958(71)90673-5.
• [12] Carrasco RC, Oncina J, Calera-Rubio J. Stochastic inference of regular tree languages. Machine Learning, 2001; 44: 185-197. doi: 10.1023/A:1010836331703.
• [13] Denis F, Habrard A. Learning rational stochastic tree languages. In: Proceedings of ALT 2007, LNAI 4754. 2007 pp. 242-256. doi: 10.1007/978-3-540-75225-7_21.
• [14] Denis F, Gilbert E, Habrard A, Ouardi F, Tommasi M. Relevant representations for the inference of rational stochastic tree languages. In: Proceedings of ICGI 2008, LNAI 5278. 2008 pp. 57-70. doi: 10.1007/978-3-540-88009-7_5.
• [15] Rico-Juan JR, Calera-Rubio J, Carrasco RC. Probabilistic k-testable tree languages. In: Proceedings of ICGI 2000, LNAI 1819. 2001 pp. 221-228. doi: 10.1007/978-3-540-45257-7_18.
• [16] Salomaa A. Probabilistic and weighted grammars. Inform. Control, 1969; 15 (6): 529-544. doi: 10.1016/S0019-9958(69)90554-3.
• [17] Manning C, Schütze H. Foundations of Statistical Natural Language Processing. MIT Press, Cambridge, MA, 1999. ISBN 9780262133609.
• [18] Durbin R, Eddy SR, Krogh A, Mitchison G. Biological Sequence Analysis: Probabilistic models of Proteins and Nucleic Acids. Cambridge Univ. Press, Cambridge, MA, 1999. ISBN 9780521629713.
• [19] Sakakibara Y, Brown M, Hughey R, Mian I, Sjolander K, Underwood R, Haussier D. Stochastic context-free grammars for tRNA modeling. Nuc. Acids Res., 1994; 22 (23): 5112-5120.
• [20] Etessami K, Stewart A, Yannakakis M. Stochastic context-free grammars, regular languages, and Newton’s method. In: Proceedings of ICALP 2013, LNCS 7966. 2013 pp. 199-211. doi: 10.1007/978-3-642-39212-2_20.
• [21] Bozapalidis S, Rahonis G. Stochastic equationality. In: Proceedings of CAI 2013, LNCS 8080. 2013 pp. 173-185. doi: 10.1007/978-3-642-40663-8_17.
• [22] Wechler W. Universal Algebra for Computer Scientists, EATCS Monographs on Theoretical Computer Science, vol. 25. Springer-Verlag, 1992. ISBN 978-3-642-76773-9. doi: 10.1007/978-3-642-76771-5.
• [23] Yeh J. Real Analysis, Theory of Measure and Integration. World Scientific, 2006.
• [24] Fülöp Z, Vogler H. Weighted tree automata and tree transducers. In: Handbook of Weighted Automata, Monographs in Theoretical Computer Science, An EATCS Series, Springer. 2009 pp. 313-404. doi: 10.1007/978-3-642-01492-5_9.
• [25] Bozapalidis S, Rahonis G. On the closure of recognizable tree series under tree homomorphisms. J. Autom. Lang. Comb., 2005; 10 (2-3): 185-202.
• [26] Lancaster P, Tismenetsky M. The Theory of Matrices. Academic Press, Inc., 1985.
• [27] Kuich W. Semirings and formal power series: Their relevance to formal languages and automata theory. In: Handbook of Formal Languages, volume 1, Chapter 9, Springer, Berlin. 1997 pp. 609-677. doi: 10.1007/978-3-642-59136-5.
• [28] Magidor M, Moran G. Probabilistic tree automata and context-free languages. Israel J. Math., 1970; 8: 340-348. doi: 10.1007/BF02798680.
• [29] Rabin MO. Probabilistic automata. Inform. Control, 1963; 6 (3): 230-245. doi: 10.1016/S0019-9958(63)90290-0.
• [30] Booth TL, Thomson RA. Applying probability measures to abstract languages. IEEE Trans. Comput.. 1973; 22 (5): 442-450. doi: 10.1109/T-C.1973.223746.
• [31] Bozapalidis S. Effective construction of the syntactic algebra of a recognizable series on trees. Acta Inform., 1991; 28 (4): 351-363. doi: 10.1007/BF01893886.
• [32] Bozapalidis S. Positive tree representations and applications to tree automata. Inform, and Comput., 1997; 139 (2): 130-153. doi: 10.1006/inco.1997.2667.
• [33] Geese R, Kovács A. Consistency of stochastic context-free grammars. Math. Comput. Modelling, 2010; 52 (3-4): 490-500. doi: 10.1016/j.mcm.2010.03.046.
• [34] Habrard A, Bernard M, Jacquenet F. Generalized stochastic tree automata for multi-relational data mining. In: Proceedings of ICGI 2002, LNAI 2484. 2002 pp. 120-133. doi: 10.1007/3-540-45790-9_10.
• [35] Habrard A, Bernard M, Jacquenet F. Multi-relational data mining in medical databases. In: Proceedings of AIME 2003, LNAI 2780. 2003 pp. 365-374. doi: 10.1007/978-3-540-39907-0_50.
• [36] Ding Y, Palmer M. Machine translation using probabilistic synchronous dependency insertion grammars. In: Proceedings of the 43rd Annual Meeting of the ACL’05. 2005 pp. 541-548. doi: 10.3115/1219840.1219907.
• [37] Knight K, Graehl J. An overview of probabilistic tree transducers for natural language processing. In: Proceedings of CICLing 2005, LNCS 3406. 2005 pp. 1-24. doi: 10.1007/978-3-540-30586-6_1.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).