eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2022-05-06
vol. 23 no. 2, special issue...
Special issues
10.46298/dmtcs.7435
7435
journal article
Universal Horn Sentences and the Joint Embedding Property
Manuel Bodirsky
Jakub Rydval
https://orcid.org/0000-0002-7961-9492
AndrĂ© Schrottenloher
The finite models of a universal sentence $\Phi$ in a finite relational
signature are the age of a structure if and only if $\Phi$ has the joint
embedding property. We prove that the computational problem whether a given
universal sentence $\Phi$ has the joint embedding property is undecidable, even
if $\Phi$ is additionally Horn and the signature of $\Phi$ only contains
relation symbols of arity at most two.
https://dmtcs.episciences.org/7435/pdf
Computer Science - Logic in Computer Science
Mathematics - Logic