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?
We review the results.
Note, although some of the material is a bit technical, no specialist knowledge is assumed, beyond elementary logic.