We consider an extension of monadic second-order logic, interpreted over the infinite binary tree, by the qualitative path-measure quantifier. This quantifier says that the set of infinite paths in the tree satisfying a formula has Lebesgue-measure one. We prove that this logic is undecidable. To do this we prove that the emptiness problem of qualitative universal parity tree automata is undecidable. Qualitative means that a run of a tree automaton is accepting if the set of paths in the run that satisfy the acceptance condition has Lebesgue-measure one. Formal languages and automata theory → Tree languages; Formal languages and automata theory → Automata over infinite objects; Logic → Higher order logic; Mathematics of computing → Probability and statistics Keywords and phrases MSO, tree automata, ω-regular conditions, almost-sure semantics Monadic Second-Order logic (MSO) is an extension of first-order logic with quantification on sets. The fundamental result about MSO is that its theory on the infinite binary tree is decidable [19]. There are a number of ways to extend this result: to structures generated by certain operations (see the survey [20]), by certain additional unary predicates [11] , and by certain generalised quantifiers [2, 15] . In this note we consider MSO+∀ =1 path , the extension of MSO by the measure-theoretic quantifier ∀ =1 path X, introduced in [14] . Here, ∀ =1 path X.ϕ states that the set of paths of the tree that satisfy ϕ has Lebesgue-measure equal to 1. This means, intuitively, that a random path almost surely satisfies ϕ, where a random path is generated by repeatedly flipping a fair coin to decide to go to left or right. A weak fragment of this * We became aware that this result was already proved by Mikołaj Bojańczyk, Edon Kelmendi and Michał Skrzypczak through a work that was conducted independently of ours [6] . Our proof technique relies on probabilistic automata, which differs from the approach of Bojańczyk et al.
More recently, Berthon et al. REF proved the slightly weaker undecidability result that emptiness is undecidable for universal parity tree automata with qualitative semantics.
Monadic Second-Order Logic with Path-Measure Quantifier is Undecidable
ArXiv
ArXiv
Mathematics Computer Science