
Amalgamation is PSPACEhard
The finite models of a universal sentence Φ in a finite relational signa...
read it

On Logics and Homomorphism Closure
Predicate logic is the premier choice for specifying classes of relation...
read it

Tractability of Quantified Temporal Constraints To The Max
A temporal constraint language is a set of relations that are firstorde...
read it

Universal Horn Sentences and the Joint Embedding Property
The finite models of a universal sentence Φ are the age of a structure i...
read it

Tractable Combinations of Temporal CSPs
The constraint satisfaction problem (CSP) of a firstorder theory T is t...
read it

Tractable Combinations of Theories via Sampling
For a firstorder theory T, the Constraint Satisfaction Problem of T is ...
read it

DatalogExpressibility for Monadic and Guarded SecondOrder Logic
We characterise the sentences in Monadic Secondorder Logic (MSO) that a...
read it

Network satisfaction for symmetric relation algebras with a flexible atom
Robin Hirsch posed in 1996 the Really Big Complexity Problem: classify t...
read it

ωcategorical structures avoiding height 1 identities
The algebraic dichotomy conjecture for Constraint Satisfaction Problems ...
read it

Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of Variables
Many combinatorial optimisation problems can be modelled as valued const...
read it

Temporal Constraint Satisfaction Problems in FixedPoint Logic
Finitedomain constraint satisfaction problems are either solvable by Da...
read it

ASNP: a tame fragment of existential secondorder logic
Amalgamation SNP (ASNP) is a fragment of existential secondorder logic ...
read it

AMSNP: a tame fragment of existential secondorder logic
Amalgamation monotone SNP (AMSNP) is a fragment of existential secondor...
read it

Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
Valued constraint satisfaction problems (VCSPs) are a large class of com...
read it

Hardness of Network Satisfaction for Relation Algebras with Normal Representations
We study the computational complexity of the general network satisfactio...
read it

Topology is relevant (in a dichotomy conjecture for infinitedomain constraint satisfaction problems)
The algebraic dichotomy conjecture for Constraint Satisfaction Problems ...
read it

Topology is relevant (in the infinitedomain dichotomy conjecture for constraint satisfaction problems)
The algebraic dichotomy conjecture for Constraint Satisfaction Problems ...
read it

Finite Relation Algebras with Normal Representations
One of the traditional applications of relation algebras is to provide a...
read it

A polynomialtime algorithm for medianclosed semilinear constraints
A subset of Q^n is called semilinear (or piecewise linear) if it is Bool...
read it

The complexity of disjunctive linear Diophantine constraints
We study the Constraint Satisfaction Problem CSP(A), where A is firstor...
read it

Classification transfer for qualitative reasoning problems
We study formalisms for temporal and spatial reasoning in the modern con...
read it

Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains
Valued constraint satisfaction problems (VCSPs) are a large class of com...
read it

A universalalgebraic proof of the complexity dichotomy for Monotone Monadic SNP
The logic MMSNP is a restricted fragment of existential secondorder log...
read it

Complexity of Combinations of Qualitative Constraint Satisfaction Problems
The CSP of a firstorder theory T is the problem of deciding for a given...
read it

Complexity Classification in InfiniteDomain Constraint Satisfaction
A constraint satisfaction problem (CSP) is a computational problem where...
read it

Tractable Set Constraints
Many fundamental problems in artificial intelligence, knowledge represen...
read it

On the Scope of the UniversalAlgebraic Approach to Constraint Satisfaction
The universalalgebraic approach has proved a powerful tool in the study...
read it
Manuel Bodirsky
is this you? claim profile