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:

We review the results.

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