Cover Image

Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pinsker, Michael, Rydval, Jakub, Schöbi, Moritz, Spiess, Christoph, Winkler, Paul
Format:	Preprint
Published:	2025
Subjects:	Logic Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra
by: Pinsker, Michael, et al.
Published: (2025)

When Darwin met Ianus: dichotomies of expressivity
by: Brunar, Johanna, et al.
Published: (2025)

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

Universal Horn Sentences and the Joint Embedding Property
by: Bodirsky, Manuel, et al.
Published: (2021)

The Golden Path to Guarded Monotone Strict NP
by: Barsukov, Alexey, et al.
Published: (2023)

Identifying Tractable Quantified Temporal Constraints within Ord-Horn
by: Rydval, Jakub, et al.
Published: (2024)

Finitely Bounded Homogeneity Turned Inside-Out
by: Rydval, Jakub
Published: (2021)

An order out of nowhere: a new algorithm for infinite-domain CSPs
by: Mottet, Antoine, et al.
Published: (2023)

The Polynomial Hierarchy and $ω$-categorical CSPs
by: Pro, Santiago Guzmán, et al.
Published: (2026)

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

Infinite trees
by: Goy, Alexandre
Published: (2025)

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

Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough
by: Mottet, Antoine, et al.
Published: (2021)

Computing with Infinite Objects: the Gray Code Case
by: Spreen, Dieter, et al.
Published: (2021)

Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting
by: Lichter, Moritz
Published: (2022)

Singleton algorithms for the Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2025)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
by: Feller, Roman, et al.
Published: (2024)

Decidability of Interpretability
by: Feller, Roman, et al.
Published: (2026)

Domain theory in univalent foundations I: Directed complete posets and Scott's $D_\infty$
by: de Jong, Tom
Published: (2024)

Discrete Homotopy and Promise Constraint Satisfaction Problem
by: Beikmohammadi, Arash, et al.
Published: (2025)

Constraint Automata on Infinite Data Trees: From CTL(Z)/CTL*(Z) To Decision Procedures
by: Demri, Stephane, et al.
Published: (2023)

Intentic Semantics for Potentialist Truthmaking
by: Gorbow, Paul
Published: (2026)

Boolean basis, formula size, and number of modal operators
by: Berkholz, Christoph, et al.
Published: (2024)

CTL* Model Checking on Infinite Families of Finite-State Labeled Transition Systems (Technical Report)
by: Pettinau, Roberto, et al.
Published: (2026)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

First-Order LTLf Synthesis with Lookback (Extended Version)
by: Winkler, Sarah
Published: (2025)

Embedded Finite Models Beyond Restricted Quantifier Collapse
by: Benedikt, Michael, et al.
Published: (2023)

Positive Almost-Sure Termination of Polynomial Random Walks
by: Winkler, Lorenz, et al.
Published: (2025)

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
by: Bodirsky, Manuel, et al.
Published: (2025)

Synthesis of Infinite State Systems
by: Drucker, Ohad, et al.
Published: (2025)

Parameterized Infinite-State Reactive Synthesis
by: Maderbacher, Benedikt, et al.
Published: (2025)

Explanations for Unrealizability of Infinite-State Safety Shields
by: Rodriguez, Andoni, et al.
Published: (2025)

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

Towards Learning Infinite SMT Models (Work in Progress)
by: Janota, Mikoláš, et al.
Published: (2025)

Infinite State Model Checking by Learning Transitive Relations
by: Frohn, Florian, et al.
Published: (2025)

Infinite Traces by Finality: a Sheaf-Theoretic Approach
by: Peressotti, Marco
Published: (2025)

Constraint Learning for Non-confluent Proof Search
by: Rawson, Michael, et al.
Published: (2026)

Localized Attractor Computations for Infinite-State Games (Full Version)
by: Schmuck, Anne-Kathrin, et al.
Published: (2024)

Modular Attractor Acceleration in Infinite-State Games (Full Version)
by: Heim, Philippe, et al.
Published: (2026)

Asynchronous Composition of LTL Properties over Infinite and Finite Traces
by: Bombardelli, Alberto, et al.
Published: (2023)