Cover Image

Low rank MSO

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bojańczyk, Mikołaj, Pilipczuk, Michał, Przybyszewski, Wojciech, Sokołowski, Marek, Stamoulis, Giannos
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

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

Flipping and Forking
by: Przybyszewski, Wojciech, et al.
Published: (2025)

Trees in graphs of large linear cliquewidth
by: Bojańczyk, Mikołaj, et al.
Published: (2025)

Rank-decreasing transductions
by: Bojańczyk, Mikołaj, et al.
Published: (2024)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

Separability Properties of Monadically Dependent Graph Classes
by: Bonnet, Édouard, et al.
Published: (2025)

The Finite Length Property of the Rado Graph and Friends
by: Yang, Jingjie, et al.
Published: (2026)

Function spaces for orbit-finite sets
by: Bojańczyk, Mikołaj, et al.
Published: (2024)

A Dichotomy Theorem for Ordinal Ranks in MSO
by: Niwiński, Damian, et al.
Published: (2025)

Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
by: Schirrmacher, Nicole, et al.
Published: (2023)

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
by: Bergougnoux, Benjamin, et al.
Published: (2025)

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

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

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

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

Efficient reversal of transductions of sparse graph classes
by: Dreier, Jan, et al.
Published: (2026)

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

3D-grids are not transducible from planar graphs
by: Gajarský, Jakub, et al.
Published: (2025)

Equilibrium Semantics and Strong Equivalence for Higher-Order Logic Programs
by: Charalambidis, Angelos, et al.
Published: (2026)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

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

Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings
by: Muñoz, Martín
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)

First-order transducibility among classes of sparse graphs
by: Gajarský, Jakub, et al.
Published: (2025)

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

On matrix rank function over bounded arithmetics
by: Ken, Eitetsu, et al.
Published: (2023)

Minor Containment and Disjoint Paths in almost-linear time
by: Korhonen, Tuukka, et al.
Published: (2024)

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
by: Pilipczuk, Michał, et al.
Published: (2025)

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

Faster diameter computation in graphs of bounded Euler genus
by: Kluk, Kacper, et al.
Published: (2025)

A Complete Quantitative Axiomatisation of Behavioural Distance of Regular Expressions
by: Różowski, Wojciech
Published: (2024)

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

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
by: Sau, Ignasi, et al.
Published: (2024)

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

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

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

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

Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
by: Sau, Ignasi, et al.
Published: (2026)