We show that the question whether a given SNP sentence defines a homogenizable class of finite structures is undecidable, even if the sentence comes from the connected Datalog fragment and uses at most binary relation symbols. As a byproduct of our proof, we also get the undecidability of some other properties for SNP sentences, e.g., whether they can be rewritten in MMSNP, or whether they define a class with a Ramsey expansion. We subsequently show that the closely related problem of testing the amalgamation property for finitely bounded classes is EXPSPACE-hard or PSPACE-hard, depending on whether the input is specified by a universal sentence or a set of forbidden substructures.
翻译:我们展示了一个问题:对于给定的SNP句子是否定义了有限结构的同质化类是不可判定的,甚至如果该句子来自于连接的Datalog片段并且最多使用二元关系符号。作为证明的副产品,我们还得到了某些其他用于SNP句子的性质的不可判定性,例如是否可以在MMSNP中重写它们,或者是否定义了一个具有Ramsey扩张的类。然后,我们证明了测试有限有界类的融合属性的问题与输入是由通用句子还是禁止子结构集合来指定有关,它们分别是EXPSPACE-hard或PSPACE-hard。