On the Borel Complexity of MSO Definable Sets of Branches
On the Borel Complexity of MSO Definable Sets of Branches
复制标题
论MSO可定义分支集的Borel复杂度
DOI：
--
复制
发表时间：
2010
影响因子：
0.8
通讯作者：
Michal Skrzypczak
中科院分区：
文献类型：
--
作者：
Mikolaj Bojanczyk;D. Niwinski;A. Rabinovich;Adam Radziwonczyk;Michal Skrzypczak
无限二进制字可以用完整二叉树中的分支来标识。我们考虑在树上的一元二阶逻辑中可定义的分支集，其中我们允许节点上有一些额外的一元谓词。我们证明了这个类等于Cantor不连续统上Borel类的集合的布尔组合。注意，最后一个与ω-正则语言的Borel复杂度一致。
An infinite binaryword can be identified with a branch in the full binary tree. We consider sets of branches definable in monadic second-order logic over the tree, where we allow some extra monadic predicates on the nodes. We show that this class equals to the Boolean combinations of sets in the Borel class Σ$^0_2$ over the Cantor discontinuum. Note that the last coincides with the Borel complexity of ω-regular languages.