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.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
|
|
