On Computing the Measures of First-Order Definable Sets of Trees

Abstract

We consider the problem of computing the measure of a regular language of infinite binary trees. While the general case remains unsolved, we show that the measure of a language defined by a first-order formula with no descendant relation or by a Boolean combination of conjunctive queries (with descendant relation) is rational and computable. Additionally, we provide an example of a first-order formula that uses descendant relation and defines a language of infinite trees having an irrational measure.

In Proceedings GandALF 2018, arXiv:1809.02416