Wadge reducibility and infinite computations

DOI10.1007/s11786-008-0042-xzbMath1157.03018OpenAlexW2043028125WikidataQ29039641 ScholiaQ29039641MaRDI QIDQ1001344

Victor L. Selivanov

Publication date: 17 February 2009

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11786-008-0042-x

zbMATH Keywords

surveycomplexityBaire spacetopologycomputabilityautomaton\(k\)-partitionWadge reducibilityBaire domain\(\omega\)-language

Mathematics Subject Classification ID

Descriptive set theory (03E15) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Determinacy principles (03E60)

Related Items

The Wadge Hierarchy of Petri Nets ω-Languages, Descriptive set theory, from Cantor to Wadge and beyond, Infinite games specified by 2-tape automata, The Wadge hierarchy on Zariski topologies, On the High Complexity of Petri Nets $$\omega $$-Languages, Two Effective Properties of ω-Rational Functions, On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets, Wadge-like reducibilities on arbitrary quasi-Polish spaces, The Diophantine equation \(x^2-(t^2+t)y^2- (4t+2)x+(4t^2+4t)y=0\), Polishness of some topologies related to word or tree automata, On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words