- Tytuł:
- The use of complexity hierarchies in descriptive set theory and automata theory
- Autorzy:
-
Andretta, A.
Camerlo, R. - Powiązania:
- https://bibliotekanauki.pl/articles/1964199.pdf
- Data publikacji:
- 2005
- Wydawca:
- Politechnika Gdańska
- Tematy:
-
hierarchies
infinite games
Borel reducibility
automata theory - Opis:
- The concept of a reduction between subsets of a given space is described, giving rise to various complexity hierarchies, studied both in descriptive set theory and in automata theory. We discuss in particular the Wadge and Lipschitz hierarchies for subsets of the Baire and Cantor spaces and the hierarchy of Borel reducibility for finitary relations on standard Borel spaces. The notions of Wadge and Lipschitz reductions are related to corresponding perfect information games.
- Źródło:
-
TASK Quarterly. Scientific Bulletin of Academic Computer Centre in Gdansk; 2005, 9, 3; 337-356
1428-6394 - Pojawia się w:
- TASK Quarterly. Scientific Bulletin of Academic Computer Centre in Gdansk
- Dostawca treści:
- Biblioteka Nauki
Artykuł