Universal Horn sentences and the joint embedding property
Discrete Mathematics & Theoretical Computer Science , Volume 23 - Issue 2 p. 4.1- 4.15
The finite models of a universal sentence Φ in a finite relational signature are the age of a structure if and only if Φ has the joint embedding property. We prove that the computational problem whether a given universal sentence Φ has the joint embedding property is undecidable, even if Φ is additionally Horn and the signature of Φ only contains relation symbols of arity at most two.
|Discrete Mathematics & Theoretical Computer Science|
Bodirsky, M, Rydval, J, & Schrottenloher, A.C. (2022). Universal Horn sentences and the joint embedding property. Discrete Mathematics & Theoretical Computer Science, 23(2), 4.1–4.15. doi:10.46298/dmtcs.7435