Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2104.11123 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929241244827648 |
|---|---|
| author | Bodirsky, Manuel Rydval, Jakub Schrottenloher, André |
| author_facet | Bodirsky, Manuel Rydval, Jakub Schrottenloher, André |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_11123 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Universal Horn Sentences and the Joint Embedding Property Bodirsky, Manuel Rydval, Jakub Schrottenloher, André Logic in Computer Science Logic 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. |
| title | Universal Horn Sentences and the Joint Embedding Property |
| topic | Logic in Computer Science Logic |
| url | https://arxiv.org/abs/2104.11123 |