|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 4 of 6 found articles
| Title: |
On the Borel Complexity of MSO Definable Sets of Branches |
| Author: |
Bojańczyk, Mikołaj Niwiński, Damian Rabinovich, Alexander Radziwończyk-Syta, Adam Skrzypczak, Michał |
| Appeared in: |
Fundamenta informaticae |
| Paging: | Volume 98 (2010) nr. 4 pages 337-349 |
| Year: |
2010-03-15 |
| Contents: |
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. |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 4 of 6 found articles
| << previous | next >> |