research
∙
09/15/2023
Forbidden Tournaments and the Orientation Completion Problem
For a fixed finite set of finite tournaments ℱ, the ℱ-free orientation p...
share
research
∙
04/25/2023
Network Satisfaction Problems Solved by k-Consistency
We show that the problem of deciding for a given finite relation algebra...
research
∙
11/07/2022
Complexity Classification Transfer for CSPs via Algebraic Products
We study the complexity of infinite-domain constraint satisfaction probl...
research
∙
05/16/2022
The Smallest Hard Trees
We find an orientation of a tree with 20 vertices such that the correspo...
research
∙
08/01/2021
Amalgamation is PSPACE-hard
The finite models of a universal sentence Φ in a finite relational signa...
research
∙
04/24/2021
On Logics and Homomorphism Closure
Predicate logic is the premier choice for specifying classes of relation...
research
∙
04/23/2021
Tractability of Quantified Temporal Constraints To The Max
A temporal constraint language is a set of relations that are first-orde...
research
∙
04/22/2021
Universal Horn Sentences and the Joint Embedding Property
The finite models of a universal sentence Φ are the age of a structure i...
research
∙
12/10/2020
Tractable Combinations of Temporal CSPs
The constraint satisfaction problem (CSP) of a first-order theory T is t...
research
∙
12/02/2020
Tractable Combinations of Theories via Sampling
For a first-order theory T, the Constraint Satisfaction Problem of T is ...
research
∙
10/12/2020
Datalog-Expressibility for Monadic and Guarded Second-Order Logic
We characterise the sentences in Monadic Second-order Logic (MSO) that a...
research
∙
08/27/2020
Network satisfaction for symmetric relation algebras with a flexible atom
Robin Hirsch posed in 1996 the Really Big Complexity Problem: classify t...
research
∙
06/13/2020
ω-categorical structures avoiding height 1 identities
The algebraic dichotomy conjecture for Constraint Satisfaction Problems ...
research
∙
03/02/2020
Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of Variables
Many combinatorial optimisation problems can be modelled as valued const...
research
∙
02/21/2020
Temporal Constraint Satisfaction Problems in Fixed-Point Logic
Finite-domain constraint satisfaction problems are either solvable by Da...
research
∙
01/22/2020
ASNP: a tame fragment of existential second-order logic
Amalgamation SNP (ASNP) is a fragment of existential second-order logic ...
research
∙
01/22/2020
AMSNP: a tame fragment of existential second-order logic
Amalgamation monotone SNP (AMSNP) is a fragment of existential second-or...
research
∙
12/18/2019
Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
Valued constraint satisfaction problems (VCSPs) are a large class of com...
research
∙
12/18/2019
Hardness of Network Satisfaction for Relation Algebras with Normal Representations
We study the computational complexity of the general network satisfactio...
research
∙
01/14/2019
Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
The algebraic dichotomy conjecture for Constraint Satisfaction Problems ...
research
∙
01/14/2019
Topology is relevant (in the infinite-domain dichotomy conjecture for constraint satisfaction problems)
The algebraic dichotomy conjecture for Constraint Satisfaction Problems ...
research
∙
10/31/2018
Finite Relation Algebras with Normal Representations
One of the traditional applications of relation algebras is to provide a...
research
∙
08/29/2018
A polynomial-time algorithm for median-closed semilinear constraints
A subset of Q^n is called semilinear (or piecewise linear) if it is Bool...
research
∙
07/03/2018
The complexity of disjunctive linear Diophantine constraints
We study the Constraint Satisfaction Problem CSP(A), where A is first-or...
research
∙
05/05/2018
Classification transfer for qualitative reasoning problems
We study formalisms for temporal and spatial reasoning in the modern con...
research
∙
04/05/2018
Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains
Valued constraint satisfaction problems (VCSPs) are a large class of com...
research
∙
02/09/2018
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
The logic MMSNP is a restricted fragment of existential second-order log...
research
∙
01/18/2018
Complexity of Combinations of Qualitative Constraint Satisfaction Problems
The CSP of a first-order theory T is the problem of deciding for a given...
research
∙
01/04/2012
Complexity Classification in Infinite-Domain Constraint Satisfaction
A constraint satisfaction problem (CSP) is a computational problem where...
research
∙
04/06/2011
Tractable Set Constraints
Many fundamental problems in artificial intelligence, knowledge represen...
research
∙
09/28/2009