3 papers
cs.LO2021
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…
cs.LO2020
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…
cs.LO2019
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…