2024/10/17 by Damian Niwiński, Niwiński, Damian, Marcin Przybyłko +3
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2410.13479
openalex created_date 2020/07/02 · openalex publication_date 2024/10/17 · openalex updated_date 2026/07/28
This work addresses the problem of computing measures of recognisable sets of infinite trees. An algorithm is provided to compute the probability measure of a tree language recognisable by a weak alternating automaton, or equivalently definable in weak monadic second-order logic. The measure is the uniform coin-flipping measure or more generally it is generated by a~branching stochastic process. The class of tree languages in consideration, although smaller than all regular tree languages, comprises in particular the languages definable in the alternation-free mu-calculus or in temporal logic CTL. Thus, the new algorithm may enhance the toolbox of probabilistic model checking.