Universal Horn Sentences and the Joint Embedding Property.

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Aufsatznummer4
Seitenumfang15
FachzeitschriftDiscrete mathematics & theoretical computer science
Jahrgang23
Ausgabenummer2
PublikationsstatusVeröffentlicht - 6 Mai 2022
Peer-Review-StatusJa

Externe IDs

ORCID /0000-0001-8228-3611/work/142241144
Scopus 85142044832
Mendeley c495ca3f-bb4f-3594-9e65-4404c9ea44c2