Implication algebras and implication semigroups of binary relations

DOI10.1007/978-3-031-28083-2_12MaRDI QIDQ6174423zbMATH OpenOpenAlexFDO

Authors Andrew Lewis-Smith, Jaš Šemrl

Publication date 17 August 2023

Published in Relational and Algebraic Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.02266

zbMATH Keywords

implication algebrasimplication semigroupsrepresentability as binary relations

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Representable implication algebras are known to be axiomatised by a finite number of equations (making the representation and finite representation problems decidable here). We show that this also holds in the context of unary (and binary) relations and present a Stone-style representation theorem. We then show that the (finite) representation decision problem is undecidable for implication semigroups, in stark contrast with implication algebras.

Recommendations

• Iimplication algebras
• scientific article; zbMATH DE number 3271476
• Relation algebras, idempotent semirings and generalized bunched implication algebras
• Generalizations of Implication Algebras
• scientific article; zbMATH DE number 908155
• Implication BL-algebras
• N-semisimple algebra and implication algebra.
• Implicational classes of De Morgan Boolean algebras
• On implicative semigroups
• scientific article; zbMATH DE number 800074

Cites work

• An algebraic approach to non-classical logics
• Embeddability and the Word Problem
• scientific article; zbMATH DE number 193143 (Why is no real title available?)
• Relation algebras as residuated Boolean algebras
• Relation algebras by games
• The structure of generalized BI-algebras and weakening relation algebras
• Undecidability of Algebras of Binary Relations
• Undecidability of representability as binary relations
• Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups
• Weakening Relation Algebras and FL^2-algebras

Cited in

(4)

• Undecidability of representability as binary relations
• scientific article; zbMATH DE number 7297870 (Why is no real title available?)
• A PROCEDURE OF IMPLICATION USING QUANTIFIABLE BINARY RELATION ON THE STRUCTURAL MODELING
• Minimal signatures with undecidability of representability by binary relations

This page was built for publication: Implication algebras and implication semigroups of binary relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174423)