Universal Horn Sentences and the Joint Embedding Property.
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
Abstract
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.
Details
Original language | English |
---|---|
Article number | 4 |
Number of pages | 15 |
Journal | Discrete mathematics & theoretical computer science |
Volume | 23 |
Issue number | 2 |
Publication status | Published - 6 May 2022 |
Peer-reviewed | Yes |
External IDs
ORCID | /0000-0001-8228-3611/work/142241144 |
---|---|
Scopus | 85142044832 |
Mendeley | c495ca3f-bb4f-3594-9e65-4404c9ea44c2 |