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…