72 citations · 368 across the 79 of their papers we have counts for
7 papers · 2 filters
Tractable Combinations of Theories via Sampling
Manuel Bodirsky, Johannes Greiner
For a first-order theory , the Constraint Satisfaction Problem of is the computational problem of deciding whether a given conjunction of atomic formulas is satisfiable in s…
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…
The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
Manuel Bodirsky, Simon Knäuer
Robin Hirsch posed in 1996 the 'Really Big Complexity Problem': classify the computational complexity of the network satisfaction problem for all finite relation algebras A. We pro…
A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
Manuel Bodirsky, Bertalan Bodor
Constraint satisfaction problems (CSPs) for first-order reducts of finitely bounded homogeneous structures form a large class of computational problems that might exhibit a complex…
ω-categorical structures avoiding height 1 identities
Manuel Bodirsky, Antoine Mottet, Miroslav Olšák +3
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial…
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…