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 ORCID-iD; 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
    Funding:
      Source : OpenAIRE Graph
    • 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

    Consultation statistics

    This page has been seen 225 times.
    This article's PDF has been downloaded 99 times.