2026-07-26T00:33:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12841 2024-03-06T10:50:49Z ddc:004 open_access

Non Axiomatisability of Positive Relation Algebras with Constants, via Graph Homomorphisms Doumane, Amina Pous, Damien Relation algebra graph homomorphisms (in)equational theories We study the equational theories of composition and intersection on binary relations, with or without their associated neutral elements (identity and full relation). Without these constants, the equational theory coincides with that of semilattice-ordered semigroups. We show that the equational theory is no longer finitely based when adding one or the other constant, refuting a conjecture from the literature. Our proofs exploit a characterisation in terms of graphs and homomorphisms, which we show how to adapt in order to capture standard equational theories over the considered signatures. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amina Doumane and Damien Pous 2020 Is Part Of LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2020.29 urn:nbn:de:0030-drops-128411 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.29 eng https://creativecommons.org/licenses/by/3.0/legalcode