Document Open Access Logo

On the Problem of Computing the Probability of Regular Sets of Trees

Authors Henryk Michalewski, Matteo Mio

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.489.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Henryk Michalewski
Matteo Mio

Cite As Get BibTex

Henryk Michalewski and Matteo Mio. On the Problem of Computing the Probability of Regular Sets of Trees. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 489-502, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.FSTTCS.2015.489

Abstract

We consider the problem of computing the probability of regular languages of infinite trees with respect to the natural coin-flipping measure. We propose an algorithm which computes the probability of languages recognizable by game automata. In particular this algorithm is applicable to all deterministic automata. We then use the algorithm to prove through examples three properties of measure: (1) there exist regular sets having irrational probability, (2) there exist comeager regular sets having probability 0 and (3) the probability of game languages W_{i,k}, from automata theory, is 0 if k is odd and is 1 otherwise.

Subject Classification

Keywords
  • regular languages of trees
  • probability
  • meta-parity games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Arnold and D. Niwiński. Rudiments of μ-calculus. Studies in Logic. North-Holland, 2001. Google Scholar
  2. André Arnold. The μ-calculus alternation-depth hierarchy is strict on binary trees. ITA, 33(4/5):329-340, 1999. Google Scholar
  3. André Arnold and Damian Niwiński. Continuous separation of game languages. Fundamenta Informaticae, 81:19-28, 2008. Google Scholar
  4. Julian C. Bradfield. The modal μ-calculus alternation hierarchy is strict. Theor. Comput. Sci., 195(2):133-153, 1998. Google Scholar
  5. Christopher W. Brown. QEPCAD B: A program for computing with semi-algebraic sets using cads. SIGSAM Bull., 37(4):97-108, 2003. Google Scholar
  6. Krishnendu Chatterjee. Stochastic ω-Regular Games. PhD thesis, University of California, Berkeley, 2007. Google Scholar
  7. Krishnendu Chatterjee, Marcin Jurdziński, and Thomas A. Henzinger. Quantitative stochastic parity games. In Proc. of SODA, pages 121-130, 2004. Google Scholar
  8. Taolue Chen, Klaus Dräger, and Stefan Kiefer. Model checking stochastic branching processes. In Proceedings of MFCS, volume 7468 of Lecture Notes in Computer Science, pages 271-282. Springer, 2012. Google Scholar
  9. Luca de Alfaro and Rupak Majumdar. Quantitative solution of omega-regular games. Journal of Computer and System Sciences, 68:374-397, 2004. Google Scholar
  10. Jacques Duparc, Alessandro Facchini, and Filip Murlak. Definable operations on weakly recognizable sets of trees. In Proc. of FSTTCS, pages 363-374, 2011. Google Scholar
  11. Alessandro Facchini, Filip Murlak, and Michal Skrzypczak. Rabin-Mostowski index problem: A step beyond deterministic automata. In Proc. of LICS, pages 499-508, 2013. Google Scholar
  12. Tomasz Gogacz, Henryk Michalewski, Matteo Mio, and Michal Skrzypczak. Measure properties of game tree languages. In Proc. MFCS, pages 303-314, 2014. Google Scholar
  13. A. S. Kechris. Classical Descriptive Set Theory. Springer Verlag, 1994. Google Scholar
  14. Henryk Michalewski and Matteo Mio. Baire Category Quantifier in Monadic Second Order Logic. In Proc. of ICALP, 2015. Google Scholar
  15. Henryk Michalewski and Matteo Mio. On the problem of computing the probability of regular sets of trees. CoRR, abs/1510.01640, 2015. Google Scholar
  16. Matteo Mio. Game Semantics for Probabilistic μ-Calculi. PhD thesis, School of Informatics, University of Edinburgh, 2012. Google Scholar
  17. Matteo Mio. Probabilistic Modal μ-Calculus with Independent product. Logical Methods in Computer Science, 8(4), 2012. Google Scholar
  18. Matteo Mio and Alex Simpson. Łukasiewicz mu-calculus. In Proc. of Workshop on Fixed Points in Computer Science, volume 126 of EPTCS, 2013. Google Scholar
  19. David E. Muller and Paul E. Schupp. Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra. Theor. Comput. Sci., 141(1&2):69-107, 1995. Google Scholar
  20. Damian Niwiński. On the cardinality of sets of infinite trees recognizable by finite automata. In Proc. MFCS, 1991. Google Scholar
  21. Damian Niwiński and Igor Walukiewicz. A gap property of deterministic tree languages. Theor. Comput. Sci., 1(303):215-231, 2003. Google Scholar
  22. Ludwig Staiger. Rich omega-words and monadic second-order arithmetic. In Proc. of CSL, pages 478-490, 1997. Google Scholar
  23. Ludwig Staiger. The Hausdorff measure of regular omega-languages is computable. Bulletin of the EATCS, 66:178-182, 1998. Google Scholar
  24. Alfred Tarski. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1951. Google Scholar
  25. Wolfgang Thomas. Languages, automata, and logic. In Handbook of Formal Languages, pages 389-455. Springer, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact