Undecidability of Algebras of Binary Relations

DOI10.1007/978-3-030-64187-0_11MaRDI QIDQ5015973zbMATH OpenOpenAlexFDO

Authors Marcel Jackson, Robin Hirsch, Ian Hodkinson

Publication date 10 December 2021

Published in Hajnal Andréka and István Németi on Unity of Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-64187-0_11

zbMATH Keywords

finite representationgroup embeddingrelation algebrarepresentationtiling problem

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) General algebraic systems (08-XX)

Recommendations

• Undecidability of representability as binary relations
• Decidability of equational theories for subsignatures of relation algebra
• Relation algebras can tile
• A decidable equational theory with undecidable membership problem for finite algebras
• Undecidable relativizations of algebras of relations

Cites work

• A perspective on the theory of relation algebras
• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• ALGORITHMIC PROBLEMS IN VARIETIES
• Boolean Algebras with Operators
• Combinatorial aspects of relations
• Completely Representable Relation Algebras
• Decidability of equational theories for subsignatures of relation algebra
• Decision problems for equational theories of relation algebras
• Embeddability and the Word Problem
• Eventually \({\mathcal H}\)-related sets and systems of equations over finite semigroups and rings
• Groups and Algebras of Binary Relations
• scientific article; zbMATH DE number 49239 (Why is no real title available?)
• scientific article; zbMATH DE number 67028 (Why is no real title available?)
• scientific article; zbMATH DE number 193143 (Why is no real title available?)
• scientific article; zbMATH DE number 1563405 (Why is no real title available?)
• scientific article; zbMATH DE number 3285224 (Why is no real title available?)
• Nonrepresentable relation algebras from groups
• Potential Divisibility in Finite Semigroups is Undecidable
• Recursive unsolvability of a problem of Thue
• Reducing first-order logic to \(\mathsf{Df}_3\), free algebras
• Relation algebras by games
• Some undecidable embedding problems for finite semigroups
• Some Varieties Containing Relation Algebras
• The calculus of relations as a foundation for mathematics
• The equational theory of CA₃ is undecidable
• The undecidability of the domino problem
• Undecidability of representability as binary relations
• Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups
• Undecidable problems for completely 0-simple semigroups.
• Unsolvability of the universal theory of finite groups

Cited in

(6)

• Undecidability of relatively free Hilbert algebras
• Undecidable theories of Lyndon algebras
• scientific article; zbMATH DE number 465525 (Why is no real title available?)
• Undecidability of representability as binary relations
• Implication algebras and implication semigroups of binary relations
• Minimal signatures with undecidability of representability by binary relations

This page was built for publication: Undecidability of Algebras of Binary Relations

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