Manuel Bodirsky ; Jakub Rydval ; André Schrottenloher
-
Universal Horn Sentences and the Joint Embedding Property
dmtcs:7435 -
Discrete Mathematics & Theoretical Computer Science,
May 6, 2022,
vol. 23 no. 2, special issue in honour of Maurice Pouzet
-
https://doi.org/10.46298/dmtcs.7435
Universal Horn Sentences and the Joint Embedding Property
Authors: Manuel Bodirsky ; Jakub Rydval ; André Schrottenloher
NULL##0000-0002-7961-9492##NULL
Manuel Bodirsky;Jakub Rydval;André Schrottenloher
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.
Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones; Funder: European Commission; Code: 681988
Algebraic Methods for Stronger Crypto; Funder: European Commission; Code: 740972
1 Document citing this article
Source : OpenCitations
Baader, Franz; Rydval, Jakub, 2022, Using Model Theory To Find Decidable And Tractable Description Logics With Concrete Domains, Journal Of Automated Reasoning, 66, 3, pp. 357-407, 10.1007/s10817-022-09626-2.