2 citations · 3 across the 7 of their papers we have counts for
10 papers
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…
The random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra
Michael Pinsker, Jakub Rydval, Moritz Schöbi +1
We prove that the random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra, hereby answering an open question of Bartošová and Scow.
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…
Finitely Bounded Homogeneity Turned Inside-Out
Jakub Rydval
Deciding the amalgamation property for a given class of finite structures is an important subroutine in classifying countable finitely homogeneous structures. We study the computat…
Universal Horn Sentences and the Joint Embedding Property
Manuel Bodirsky, Jakub Rydval, André Schrottenloher
The finite models of a universal sentence in a finite relational signature are the age of a structure if and only if has the joint embedding property. We prove that the com…
Tractable Combinations of Temporal CSPs
Manuel Bodirsky, Johannes Greiner, Jakub Rydval
The constraint satisfaction problem (CSP) of a first-order theory T is the computational problem of deciding whether a given conjunction of atomic formulas is satisfiable in some m…
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems
Manuel Bodirsky, Jakub Rydval
Finite-domain constraint satisfaction problems are either solvable by Datalog, or not even expressible in fixed-point logic with counting. The border between the two regimes coinci…