Undecidability of representability as binary relations
From MaRDI portal
Publication:4899169
DOI10.2178/jsl.7704090zbMath1279.03084MaRDI QIDQ4899169
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
representability; relation algebra; binary relations; Brandt semigroup; lattice-ordered monoid; Boolean monoid
03B25: Decidability of theories and sets of sentences
03G15: Cylindric and polyadic algebras; relation algebras
Related Items
Undecidability of Algebras of Binary Relations, Constructing and embedding mutually orthogonal Latin squares: reviewing both new and existing results, Finite representability of semigroups with demonic refinement, The algebra of functions with antidomain and range, Embeddability into relational lattices is undecidable, Small partial Latin squares that embed in an infinite group but not into any finite group, Domain and range for angelic and demonic compositions, Ehresmann theory and partition monoids, Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups
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