Undecidability of representability as binary relations

DOI10.2178/jsl.7704090zbMath1279.03084OpenAlexW2167982168MaRDI QIDQ4899169

Marcel Jackson, Robin Hirschl

Publication date: 7 January 2013

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.jsl/1350315584

zbMATH Keywords

representabilityrelation algebrabinary relationsBrandt semigrouplattice-ordered monoidBoolean monoid

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Cylindric and polyadic algebras; relation algebras (03G15)

Related Items (10)

Finite representability of semigroups with demonic refinement ⋮ Embeddability into relational lattices is undecidable ⋮ Small partial Latin squares that embed in an infinite group but not into any finite group ⋮ Implication algebras and implication semigroups of binary relations ⋮ The algebra of functions with antidomain and range ⋮ Domain and range for angelic and demonic compositions ⋮ Ehresmann theory and partition monoids ⋮ Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups ⋮ Constructing and embedding mutually orthogonal Latin squares: reviewing both new and existing results ⋮ Undecidability of Algebras of Binary Relations

Cites Work

• Relation algebras by games
• The representation of relation algebras. II
• Algebras of modal operators and partial correctness
• Relation algebras
• Undecidable problems for completely 0-simple semigroups.
• Atom structures and Sahlqvist equations
• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• The equational theory of union-free algebras of relations
• A remark of representable positive cylindric algebras
• Representations of distributive lattice-ordered semigroups with binary relations
• Representable semilattice-ordered monoids
• On representable relation algebras
• Relation algebras and function semigroups
• Undecidability and nonperiodicity for tilings of the plane
• The representation of relational algebras
• Representability is not decidable for finite relation algebras
• MODAL RESTRICTION SEMIGROUPS: TOWARDS AN ALGEBRA OF FUNCTIONS
• Partial Maps with Domain and Range: Extending Schein's Representation
• PDL with intersection and converse: satisfiability and infinite-state model checking
• Free right type A semigroups
• Difference semigroups
• ALGORITHMIC PROBLEMS IN VARIETIES
• Kleene algebra with domain
• Canonical varieties with no canonical axiomatisation
• The Class of Representable Ordered Monoids has a Recursively Enumerable, Universal Axiomatisation but it is Not Finitely Axiomatisable
• FAITHFUL FUNCTORS FROM CANCELLATIVE CATEGORIES TO CANCELLATIVE MONOIDS WITH AN APPLICATION TO ABUNDANT SEMIGROUPS
• Boolean Algebras with Operators
• An invitation to \(C\)-semigroups

This page was built for publication: Undecidability of representability as binary relations