Cover Image

A Dichotomy Theorem for Ordinal Ranks in MSO

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Niwiński, Damian, Parys, Paweł, Skrzypczak, Michał
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Computability of Measures of Regular Sets of Infinite Trees
by: Niwiński, Damian, et al.
Published: (2023)

Generalised Quantifiers Based on Rabin-Mostowski Index
by: Kuperberg, Denis, et al.
Published: (2026)

Subsumption in $\mathcal{FL}_{\bot \mathit{reg}}$ with TBoxes Is in ExpTime
by: Henne, Michał, et al.
Published: (2026)

Computing measures of weak-MSO definable sets of trees
by: Niwiński, Damian, et al.
Published: (2024)

Low rank MSO
by: Bojańczyk, Mikołaj, et al.
Published: (2025)

Positionality in $Σ_0^2$ and a completeness result
by: Ohlmann, Pierre, et al.
Published: (2023)

Ranked Enumeration for MSO on Trees via Knowledge Compilation
by: Amarilli, Antoine, et al.
Published: (2023)

Decidability of MSO Reparameterization over Countable Chains
by: Rabinovich, Alexander
Published: (2026)

Partially Finite Model Reasoning in Description Logics Extended Version
by: Gogacz, Tomasz, et al.
Published: (2026)

Tree algebras and bisimulation-invariant MSO on finite graphs
by: Colcombet, Thomas, et al.
Published: (2024)

A Dichotomy Theorem for Automatic Structures
by: Cuvelier, Antoine, et al.
Published: (2026)

Constructive Ordinal Exponentiation
by: de Jong, Tom, et al.
Published: (2025)

Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
by: Mählmann, Nikolas
Published: (2025)

Scoped MSO, Register Automata, and Expressions: Equivalence over Data Words
by: Piórkowski, Radosław
Published: (2026)

Graph neural networks and MSO
by: Ahvonen, Veeti, et al.
Published: (2025)

Tabular intermediate logics comparison
by: Rzążewski, Paweł, et al.
Published: (2025)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2024)

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
by: Dreier, Jan, et al.
Published: (2024)

Comparing and Contrasting Arrow's Impossibility Theorem and Gödel's Incompleteness Theorem
by: Livson, Ori, et al.
Published: (2025)

Dichotomy for Axiomatising Inclusion Dependencies on K-Databases
by: Hannula, Miika, et al.
Published: (2026)

FO logic on cellular automata orbits equals MSO logic
by: Theyssier, Guillaume
Published: (2024)

MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras
by: Kleest-Meißner, Sarah, et al.
Published: (2022)

A note on Stone-Čech compactification in ZFA
by: Przybyłek, Michał R.
Published: (2023)

Fixed Point Theorems in Computability Theory
by: Terwijn, Sebastiaan A.
Published: (2024)

The structure of polynomial growth for tree automata/transducers and MSO set queries
by: Gallot, Paul, et al.
Published: (2025)

An Analysis of Tennenbaum's Theorem in Constructive Type Theory
by: Hermes, Marc, et al.
Published: (2023)

DRAFT: A Formally Verified Constructive Proof of the Consistency of Peano Arithmetic Using Ordinal Assignments
by: Bryce, Aaron, et al.
Published: (2026)

Effective MSO-Definability for Tree-width Bounded Models of an Inductive Separation Logic of Relations
by: Bueri, Lucas, et al.
Published: (2024)

Gödel Incompleteness Theorem for PAC Learnable Theory from the view of complexity measurement
by: Ma, Zhifeng, et al.
Published: (2024)

Ordinal measures of the set of finite multisets
by: Vialard, Isa
Published: (2023)

HistMSO: A Logic for Reasoning about Consistency Models with MONA
by: Coget, Isabelle, et al.
Published: (2026)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
Published: (2024)

T-BAT semantics and its logics
by: Pawlowski, Pawel
Published: (2025)

Compositional Control-Driven Boolean Circuits
by: Arellanes, Damian
Published: (2025)

Colimit-Based Composition of High-Level Computing Devices
by: Arellanes, Damian
Published: (2026)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
by: Zhuk, Dmitriy
Published: (2024)

Monadic Second-Order Logic of Permutations
by: Jelínek, Vít, et al.
Published: (2025)

Advances in Algorithmic Meta Theorems
by: Siebertz, Sebastian, et al.
Published: (2024)

A No-go Theorem for Coalgebraic Product Construction
by: Kori, Mayuko, et al.
Published: (2025)

The complete classification for quantified equality constraints
by: Zhuk, Dmitriy, et al.
Published: (2021)