Stochastic Semantics

Article type: Research Article

Authors: Bozapalidis, Symeon | Rahonis, George^*

Affiliations: Department of Mathematics, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece. bozapali@math.auth.gr, grahonis@math.auth.gr

Correspondence: [*] Address for correspondence: Department of Mathematics, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece.

Abstract: 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.

Keywords: Stochastic algebras, systems of stochastic trees series, stochastic context-free grammars

DOI: 10.3233/FI-2017-1463

Journal: Fundamenta Informaticae, vol. 150, no. 2, pp. 143-177, 2017