文章基本信息

标题：Non Axiomatisability of Positive Relation Algebras with Constants, via Graph Homomorphisms
本地全文：下载
作者：Amina Doumane ; Damien Pous
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：171
页码：29:1-29:16
DOI：10.4230/LIPIcs.CONCUR.2020.29
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Relation algebra; graph homomorphisms; (in)equational theories