2018/09/10 by Marcin Przybyłko
Computer Science · #cs.CC #cs.LO
paper · pdf · doi:10.4204/eptcs.277.15
published as EPTCS 277, 2018, pp. 206-219 · In Proceedings GandALF 2018, arXiv:1809.02416
arxiv created 2018/09/10 · arxiv updated 2018/09/11
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.