10.46298/dmtcs.7435
https://dmtcs.episciences.org/7435
Bodirsky, Manuel
Manuel
Bodirsky
Rydval, Jakub
Jakub
Rydval
Schrottenloher, AndrĂ©
AndrĂ©
Schrottenloher
Universal Horn Sentences and the Joint Embedding Property
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.
Comment: 16 pages
episciences.org
Computer Science - Logic in Computer Science
Mathematics - Logic
arXiv.org - Non-exclusive license to distribute
2022-04-09
2022-05-06
2022-05-06
eng
journal article
arXiv:2104.11123
10.48550/arXiv.2104.11123
1365-8050
https://dmtcs.episciences.org/7435/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
vol. 23 no. 2, special issue in honour of Maurice Pouzet
Special issues
Researchers
Students