2022-05-06
Universal Horn sentences and the joint embedding property
Publication
Publication
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.
Additional Metadata | |
---|---|
, , | |
doi.org/10.46298/dmtcs.7435 | |
Discrete Mathematics & Theoretical Computer Science | |
Algebraic Methods for Stronger Crypto | |
Organisation | Cryptology |
Bodirsky, M., Rydval, J., & Schrottenloher, A. (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 |