The finite models of a universal sentence $Phi$ in a finite relational signature are the age of a homogeneous structure if and only if $Phi$ has the amalgamation property. We prove that the computational problem whether a given universal sentence $Phi$ has the amalgamation property is PSPACE-hard, even if $Phi$ is additionally Horn and the signature of $Phi$ only contains relation symbols of arity at most three. The decidability of the problem remains open.
تحميل البحث