2026-07-22T06:37:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5639 2024-03-06T10:36:46Z ddc:004 open_access

On the Problem of Computing the Probability of Regular Sets of Trees Michalewski, Henryk Mio, Matteo regular languages of trees probability meta-parity games 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henryk Michalewski and Matteo Mio 2015 Is Part Of LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2015.489 urn:nbn:de:0030-drops-56390 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.489 eng https://creativecommons.org/licenses/by/3.0/legalcode