THE USE OF COMPLEXITY HIERARCHIES IN DESCRIPTIVE SET THEORY AND AUTOMATA THEORY

Abstract

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.

Keywords

• hierarchies
• infinite games
• Borel reducibility
• automata theory