概要：

We consider the (un)decidability and complexity of equational theories of calculi of relations. Calculi of relations are algebraic systems with operations on binary relations (such as union, intersection, complement, composition, converse, and transitive closure).

In this talk, after introducing Tarski's calculus of relations, we focus on some equational theories of ``existential'' calculi of relations, give sketches of the (un)decidability and complexity results, and give open problems.

Here, ``existential'' means that complement only applies to constants or variables. Such fragments are related with existential logics.