Wadge degrees of infinitary rational relations

DOI10.1007/s11786-008-0045-7zbMath1157.03017arXiv0804.3266MaRDI QIDQ1001349

Olivier Finkel

Publication date: 17 February 2009

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

Full work available at URL: https://arxiv.org/abs/0804.3266

zbMATH Keywords

topological complexity; Borel hierarchy; Wadge hierarchy; complete sets; Cantor topology; infinitary rational relations; 2-tape Büchi automata; Wadge degrees; Wadge games

Mathematics Subject Classification ID

03E15: Descriptive set theory

03D05: Automata and formal grammars in connection with logical questions

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D10: Turing machines and related notions