Homogeneity and Homogenizability: Hard Problems for the Logic SNP
From MaRDI portal
Publication:6507609
arXiv2108.00452MaRDI QIDQ6507609FDOQ6507609
Authors: Jakub Rydval 
Abstract: 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 Datalog programs, e.g., whether they can be rewritten in MMSNP, whether they solve some finite-domain CSP, or whether they define the age of a reduct of a homogeneous Ramsey structure in a finite relational signature. 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.
This page was built for publication: Homogeneity and Homogenizability: Hard Problems for the Logic SNP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507609)
