Buchumschlag

Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Mottet, Antoine, Nagy, Tomáš, Pinsker, Michael, Wrona, Michał
Format:	Preprint
Veröffentlicht:	2021
Schlagworte:	Logic in Computer Science
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An order out of nowhere: a new algorithm for infinite-domain CSPs
von: Mottet, Antoine, et al.
Veröffentlicht: (2023)

Algebraic and algorithmic synergies between promise and infinite-domain CSPs
von: Mottet, Antoine
Veröffentlicht: (2025)

Strict width for Constraint Satisfaction Problems over homogeneous strucures of finite duality
von: Nagy, Tomáš, et al.
Veröffentlicht: (2024)

The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
von: Brunar, Johanna, et al.
Veröffentlicht: (2025)

Complexity Classification Transfer for CSPs via Algebraic Products
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2022)

Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation)
von: Wrona, Michal
Veröffentlicht: (2024)

The complete classification for quantified equality constraints
von: Zhuk, Dmitriy, et al.
Veröffentlicht: (2021)

When Darwin met Ianus: dichotomies of expressivity
von: Brunar, Johanna, et al.
Veröffentlicht: (2025)

Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
von: Pinsker, Michael, et al.
Veröffentlicht: (2025)

Identifying Tractable Quantified Temporal Constraints within Ord-Horn
von: Rydval, Jakub, et al.
Veröffentlicht: (2024)

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
von: Nagy, Tomáš, et al.
Veröffentlicht: (2025)

How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
von: Benedikt, Michael, et al.
Veröffentlicht: (2026)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
von: Feller, Roman, et al.
Veröffentlicht: (2024)

Being polite is not enough (and other limits of theory combination)
von: Toledo, Guilherme V., et al.
Veröffentlicht: (2025)

Model-checking positive equality free logic on a fixed structure (direttissima)
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2024)

Embedded Finite Models Beyond Restricted Quantifier Collapse
von: Benedikt, Michael, et al.
Veröffentlicht: (2023)

Decidability of Interpretability
von: Feller, Roman, et al.
Veröffentlicht: (2026)

The Polynomial Hierarchy and $ω$-categorical CSPs
von: Pro, Santiago Guzmán, et al.
Veröffentlicht: (2026)

Satisfiability of commutative vs. non-commutative CSPs
von: Bulatov, Andrei A., et al.
Veröffentlicht: (2024)

Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2025)

Restricted CSPs and F-free Digraph Algorithmics
von: Guzmán-Pro, Santiago, et al.
Veröffentlicht: (2025)

Notes on CSPs and Polymorphisms
von: Brady, Zarathustra
Veröffentlicht: (2022)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

A note on Stone-Čech compactification in ZFA
von: Przybyłek, Michał R.
Veröffentlicht: (2023)

The Golden Path to Guarded Monotone Strict NP
von: Barsukov, Alexey, et al.
Veröffentlicht: (2023)

On matrix rank function over bounded arithmetics
von: Ken, Eitetsu, et al.
Veröffentlicht: (2023)

The Qualitative Collapse of Concurrent Games
von: Clairambault, Pierre
Veröffentlicht: (2024)

Tighter Bounds for Query Answering with Guarded TGDs
von: Amarilli, Antoine, et al.
Veröffentlicht: (2022)

On the consistency of stronger lower bounds for NEXP
von: Thapen, Neil
Veröffentlicht: (2025)

Computation by infinite descent made explicit
von: Enqvist, Sebastian
Veröffentlicht: (2025)

Monadic Second-Order Logic of Permutations
von: Jelínek, Vít, et al.
Veröffentlicht: (2025)

Arity hierarchies for quantifiers closed under partial polymorphisms
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

Capturing the polynomial hierarchy by second-order revised Krom logic
von: Wang, Kexu, et al.
Veröffentlicht: (2022)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
von: Zhang, Tianwei, et al.
Veröffentlicht: (2024)

On the Axioms of Arboreal Categories
von: Jakl, Tomáš, et al.
Veröffentlicht: (2026)

Computable domains of a Halting Function
von: Peralta, Abel Luis
Veröffentlicht: (2024)

Four imprints of Belnap's useful four-valued logic in computer science
von: Jakl, Tomáš
Veröffentlicht: (2025)

Collapsing Constructive and Intuitionistic Modal Logics
von: Pacheco, Leonardo
Veröffentlicht: (2024)

Tabular intermediate logics comparison
von: Rzążewski, Paweł, et al.
Veröffentlicht: (2025)

Proceedings Eleventh International Conference on Non-Classical Logics. Theory and Applications
von: Indrzejczak, Andrzej, et al.
Veröffentlicht: (2024)