论文标题
简单常规树的均匀度量
The Uniform Measure of Simple Regular Sets of Infinite Trees
论文作者
论文摘要
我们考虑计算一组无限二进制树的度量的问题。尽管一般情况尚未解决，但我们表明，在以下三种形式主义之一中给出集合时可以计算一种语言的度量：一个没有后代关系的一阶公式；连接性查询的布尔组合（具有后代关系）；或通过非确定性安全树自动机。此外，在前两种情况下，该集合的度量始终是理性的，而在第三个情况下，这是代数数。此外，我们提供了使用后代关系的一阶公式的示例，并定义了具有非理性（但代数）度量的无限树的语言。
We consider the problem of computing the measure of a regular set of infinite binary trees. While the general case remains unsolved, we show that the measure of a language can be computed when the set is given in one of the following three formalisms: a first-order formula with no descendant relation; a Boolean combination of conjunctive queries (with descendant relation); or by a non-deterministic safety tree automaton. Additionally, in the first two cases the measure of the set is always rational, while in the third it is an algebraic number. Moreover, we provide an example of a first-order formula that uses descendant relation and defines a language of infinite trees having an irrational (but algebraic) measure.
