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 PropertyArticle

Authors: Manuel Bodirsky ; Jakub Rydval ORCID; 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.

    Comment: 16 pages

    https://doi.org/10.46298/dmtcs.7435
    Source: arXiv.org:2104.11123
    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
    Licence: arXiv.org - Non-exclusive license to distribute
    Funding:
      Source : OpenAIRE Graph
    • Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones; Funder: European Commission; Code: 681988
    • Incentive - LA 1 - 2013; Funder: Fundação para a Ciência e a Tecnologia, I.P.; Code: Incentivo/SAU/LA0001/2013
    • Incentive - LA 2 - 2013; Funder: Fundação para a Ciência e a Tecnologia, I.P.; Code: Incentivo/SAU/LA0002/2013
    • Quantitative Logics and Automata; Funder: Deutsche Forschungsgemeinschaft; Code: 189782547/GRK 1763
    • Algebraic Methods for Stronger Crypto; Funder: European Commission; Code: 740972

    1 Document citing this article

    Share and export

    Consultation statistics

    This page has been seen 751 times.
    This article's PDF has been downloaded 415 times.