2 citations · 2 across the 3 of their papers we have counts for
7 papers
Network Satisfaction over Four-Atom Relation Algebras: Complexity and Representations
Manuel Bodirsky, Moritz Jahn, Simon Knäuer +2
Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Cristani and Hirsch showed that the netw…
Network Satisfaction Problems Solved by k-Consistency
Manuel Bodirsky, Simon Knäuer
We show that the problem of deciding for a given finite relation algebra A whether the network satisfaction problem for A can be solved by the k-consistency procedure, for some nat…
On Logics and Homomorphism Closure
Manuel Bodirsky, Thomas Feller, Simon Knäuer +1
Predicate logic is the premier choice for specifying classes of relational structures. Homomorphisms are key to describing correspondences between relational structures. Questions…
Datalog-Expressibility for Monadic and Guarded Second-Order Logic
Manuel Bodirsky, Simon Knäuer, Sebastian Rudolph
We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also s…
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…
ASNP: a tame fragment of existential second-order logic
Manuel Bodirsky, Simon Knäuer, Florian Starke
Amalgamation SNP (ASNP) is a fragment of existential second-order logic that strictly contains binary connected MMSNP of Feder and Vardi and binary guarded monotone SNP of Bienvenu…
Hardness of Network Satisfaction for Relation Algebras with Normal Representations
Manuel Bodirsky, Simon Knäuer
We study the computational complexity of the general network satisfaction problem for a finite relation algebra with a normal representation . If contains a non-trivial…