Bulletin of Symbolic Logic 25 (2):221-222 (2019)

The thesis focuses on a quite recent research field lying in between Descriptive Set Theory and Automata Theory (for infinite objects). In both areas, one is often concerned with subsets of the Cantor space or of its homeomorphic copies. In Descriptive Set Theory, such subsets are usually stratified in topological hierarchies, like the Borel hierarchy, the Wadge hierarchy and the difference hierarchy; in Automata Theory, such sets are studied in terms of regularity, that is, the property of being recognised by an automaton or, equivalently, of being expressible in Monadic Second-Order Logic. This double point of view leads to many interesting questions about the interplay and relationship between topological complexity and regularity. While we have a complete picture of what happens in the case of automata on words, the case of automata on trees is still a terra incognita. Some results have already been obtained for particular classes of languages, like Buchi languages, deterministic languages, ¨ and unambiguous languages. In this thesis we instead drop any restriction and prove some new results concerning arbitrary regular tree languages which belong to low levels of the Borel hierarchy and of the Wadge hierarchy.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/bsl.2019.12
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 54,385
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Topological Complexity of Locally Finite Ω-Languages.Olivier Finkel - 2008 - Archive for Mathematical Logic 47 (6):625-651.
Long Borel Hierarchies.Arnold W. Miller - 2008 - Mathematical Logic Quarterly 54 (3):307-322.
Mass Problems and Measure-Theoretic Regularity.Stephen G. Simpson - 2009 - Bulletin of Symbolic Logic 15 (4):385-409.
Two Simple Sets That Are Not Positively Borel.Wim Veldman - 2005 - Annals of Pure and Applied Logic 135 (1-3):151-209.
Squares of Regular Languages.Gerhard Lischke - 2005 - Mathematical Logic Quarterly 51 (3):299.
The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2005 - Archive for Mathematical Logic 45 (3):323-350.
The Fine Structure of the Intuitionistic Borel Hierarchy.Wim Veldman - 2009 - Review of Symbolic Logic 2 (1):30-101.
Regular Reals.Guohua Wu - 2005 - Mathematical Logic Quarterly 51 (2):111-119.


Added to PP index

Total views
3 ( #1,267,372 of 2,362,053 )

Recent downloads (6 months)
2 ( #362,425 of 2,362,053 )

How can I increase my downloads?


My notes