research
∙
04/25/2023
Network Satisfaction Problems Solved by k-Consistency
We show that the problem of deciding for a given finite relation algebra...
share
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
∙
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
∙
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