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

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.


Volume: vol. 23 no. 2, special issue in honour of Maurice Pouzet
Section: Special issues
Published on: May 6, 2022
Accepted on: April 9, 2022
Submitted on: May 2, 2021
Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic


Share

Consultation statistics

This page has been seen 64 times.
This article's PDF has been downloaded 35 times.