Representability is not decidable for finite relation algebras

DOI10.1090/S0002-9947-99-02264-3MaRDI QIDQ2701663zbMATH OpenOpenAlexFDO

Authors Robin Hirsch, Ian Hodkinson

Publication date 19 February 2001

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/s0002-9947-99-02264-3

zbMATH Keywords

algebraic logicgamesrelation algebrarepresentationtiling problemundecidability

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Cylindric and polyadic algebras; relation algebras (03G15) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) 2-person games (91A05)

Recommendations

• Undecidability of representability as binary relations
• Relation algebras can tile
• Relation algebras by games
• Non-representable relation algebras from vector spaces
• Weakly representable but not representable relation algebras

Cites work

• A perspective on the theory of relation algebras
• Atom structures of cylindric algebras and relation algebras
• Boolean Algebras with Operators
• Complete representations in algebraic logic
• Completely Representable Relation Algebras
• Cylindric algebras. Part I. With an introductory chapter: General theory of algebras. 2nd printing
• scientific article; zbMATH DE number 67035 (Why is no real title available?)
• scientific article; zbMATH DE number 193143 (Why is no real title available?)
• On representable relation algebras
• Some Varieties Containing Relation Algebras
• Step by step – Building representations in algebraic logic
• The representation of relation algebras. II
• The representation of relational algebras
• The undecidability of the domino problem

Cited in

(31)

• Atom structures of cylindric algebras and relation algebras
• Embeddability into relational lattices is undecidable
• Algebraic foundations for qualitative calculi and networks
• A construction of cylindric and polyadic algebras from atomic relation algebras
• Relation algebras can tile
• Ehresmann theory and partition monoids
• Reducts of relation algebras: the aspects of axiomatisability and finite representability
• Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups
• Positive fragments of relevance logic and algebras of binary relations
• Modal restriction semigroups: towards an algebra of functions.
• Undecidability of First-Order Intuitionistic and Modal Logics with Two variables
• Nonrepresentable relation algebras from groups
• Partial Maps with Domain and Range: Extending Schein's Representation
• Finite algebras of relations are representable on finite sets
• On modal logics betweenK × K × KandS5 × S5 × S5
• Undecidability of representability as binary relations
• Recursive axiomatisations from separation properties
• Low growth equational complexity
• Embeddability into relational lattices is undecidable
• Algebraic Logic, Where Does it Stand Today?
• Relational lattices via duality
• Relation algebras from cylindric algebras. I
• Relation algebras from cylindric algebras. II
• Finite, integral, and finite-dimensional relation algebras: A brief history
• Edge colourings and qualitative representations of chromatic algebras
• Network satisfaction problems solved by k-consistency
• Minimal signatures with undecidability of representability by binary relations
• Representable distributive quasi relation algebras
• Cyclic group spectra for some small relation algebras
• Representability of Ramsey relation algebras
• The algebra of functions with antidomain and range

This page was built for publication: Representability is not decidable for finite relation algebras

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