5 papers · 1 filter
Deciding Amalgamation Beyond Arity Two: The Semantic Horn Case
Jakub Rydval
We study the amalgamation decision problem (ADP): given a universal first-order sentence , decide whether the class of its finite models has the amalgamation pr…
The Polynomial Hierarchy and -categorical CSPs
Santiago Guzmán Pro, Jakub Rydval
In 2008, Bodirsky and Grohe showed that for every -level of the Polynomial Hierarchy (PH) there are -categorical Constraint Satisfaction Problems (CSPs) comple…
Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
Michael Pinsker, Jakub Rydval, Moritz Schöbi +2
The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain wel…
Identifying Tractable Quantified Temporal Constraints within Ord-Horn
Jakub Rydval, Žaneta Semanišinová, Michał Wrona
The constraint satisfaction problem, parameterized by a relational structure, provides a general framework for expressing computational decision problems. Already the restriction t…
The Golden Path to Guarded Monotone Strict NP
Alexey Barsukov, Michael Pinsker, Jakub Rydval
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment and…