Undecidability of algebras of relations

Robin Hirsch

When handling algebras of binary relations, e.g. using Kleene Algebra, Relation Algebra, or other algebras, various computational questions naturally arise:

• Is the equational theory of the class of algebras decidable (and if so, what is its complexity)?
• Is it decidable whether a finite abstract algebra of a given signature is isomorphic to a concrete algebra of binary relations, is it decidable whether such an algebra is isomorphic to a concrete algebra of binary relations over a finite base?

Note, although some of the material is a bit technical, no specialist knowledge is assumed, beyond elementary logic.