Well-Quasi Orders and Hierarchy Theory

DOI10.1007/978-3-030-30229-0_10zbMath1496.03189arXiv1809.02941OpenAlexW2892315907MaRDI QIDQ3295154

Victor L. Selivanov

Publication date: 8 July 2020

Published in: Trends in Logic (Search for Journal in Brave)

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

zbMATH Keywords

reducibilityBorel hierarchyWadge hierarchywell-quasi-order\(k\)-partitionlabeled tree\(h\)-quasiorderfine hierarchybetter quasiorderquasi-Polish spaceHausdorff hierarchy

Mathematics Subject Classification ID

Partial orders, general (06A06) Descriptive set theory (03E15) Partition relations (03E02) Hierarchies of computability and definability (03D55)

Cites Work

• Definability in the substructure ordering of simple graphs
• Efficient algorithms for membership in Boolean hierarchies of regular languages
• Fine hierarchies via Priestley duality
• A Wadge hierarchy for second countable spaces
• Fragments of first-order logic over infinite words
• Forcing absoluteness and regularity properties
• Graph minors. XX: Wagner's conjecture
• On regularity of context-free languages
• Hierarchies of hyperarithmetical sets and functions
• Towards a descriptive set theory for domain-like structures
• More on Wadge determinacy
• Preservation of the Borel class under countable-compact-covering mappings
• On the state complexity of closures and interiors of regular languages with subwords and superwords
• Fine hierarchies and m-reducibilities in theoretical computer science
• Definability in substructure orderings. II: Finite ordered sets
• Definability in the \(h\)-quasiorder of labeled forests
• Definability in substructure orderings. I: Finite semilattices
• Definability in substructure orderings. IV: Finite lattices
• Definability in substructure orderings. III: Finite distributive lattices
• Structure of degrees of generalized index sets
• Characterizations of some classes of regular events
• Algorithmic complexity of algebraic systems
• Fine hierarchy of regular \(\omega\)-languages
• Polynomial-time versus recursive models
• Computable structures and the hyperarithmetical hierarchy
• Continuous reducibility and dimension of metric spaces
• Using forward reachability analysis for verification of lossy channel systems
• Well-quasi-orders and regular \(\omega\)-languages
• Quasi-Polish spaces
• Extending Wadge theory to \(k\)-partitions
• Definability in the embeddability ordering of finite directed graphs
• Generalized Post embedding problems
• Computable linearizations of well-partial-orderings
• On Fraissé's order type conjecture
• A reducibility for the dot-depth hierarchy
• Undecidable theories
• Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
• Weihrauch Degrees, Omniscience Principles and Weak Computability
• Effective Choice and Boundedness Principles in Computable Analysis
• A classification of jump operators
• A Fine Hierarchy of ω-Regular k-Partitions
• Slicing the Truth
• Separation principles in the hierarchies of classical and effective descriptive set theory
• Theories of orders on the set of words
• The quotient algebra of labeled forests modulo h-equivalence
• Hierarchies and reducibilities on regular languages related to modulo counting
• A Gandy Theorem for Abstract Structures and Applications to First-Order Definability
• Definability in the Subword Order
• Borel-amenable reducibilities for sets of reals
• Definability in the Infix Order on Words
• A characterization of jump operators
• On ω-regular sets
• Borel–Wadge degrees
• Linear algebraic groups and countable Borel equivalence relations
• Towards a descriptive theory of cb₀-spaces
• Borel subsets of the real line and continuous reducibility
• The uniform Martin’s conjecture for many-one degrees
• Fine hierarchies and Boolean terms
• Total Representations
• Martin's conjecture, arithmetic equivalence, and countable Borel equivalence relations
• The Height of Piecewise-Testable Languages with Applications in Logical Complexity
• Definability in First Order Theories of Graph Orderings
• A quasi-order on continuous functions
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• On the structure of the Wadge degrees of bqo-valued Borel functions
• Definability in the Homomorphic Quasiorder of Finite Labeled Forests
• Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Solving Sequential Conditions by Finite-State Strategies
• Wadge-like reducibilities on arbitrary quasi-Polish spaces
• Ordering by Divisibility in Abstract Algebras
• Logical Approaches to Computational Barriers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Well-Quasi Orders and Hierarchy Theory