Universal Horn Sentences and the Joint Embedding Property.
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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
Originalsprache | Undefiniert |
---|---|
Aufsatznummer | 4 |
Fachzeitschrift | Discrete mathematics & theoretical computer science |
Jahrgang | abs/2104.11123 |
Ausgabenummer | 2 |
Publikationsstatus | Veröffentlicht - 2021 |
Peer-Review-Status | Ja |
Externe IDs
ORCID | /0000-0001-8228-3611/work/142241144 |
---|---|
Scopus | 85142044832 |