2026-08-13T18:15:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14481 2024-03-06T10:54:07Z ddc:004 open_access

Graph Characterization of the Universal Theory of Relations Doumane, Amina Relation algebra Graph homomorphism Equational theories First-order logic The equational theory of relations can be characterized using graphs and homomorphisms. This result, found independently by Freyd and Scedrov and by Andréka and Bredikhin, shows that the equational theory of relations is decidable. In this paper, we extend this characterization to the whole universal first-order theory of relations. Using our characterization, we show that the positive universal fragment is also decidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amina Doumane 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.41 urn:nbn:de:0030-drops-144815 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.41 eng https://creativecommons.org/licenses/by/4.0/legalcode