  We study the decidability and complexity of equational theories of the
existential calculus of relations with transitive closure (ECoR*) and its
fragments, where ECoR* is the positive calculus of relations with transitive
closure extended with complements of term variables and constants. We give
characterizations of these equational theories by using edge saturations and we
show that the equational theory is 1) coNP-complete for ECoR* without
transitive closure; 2) in coNEXP for ECoR* without intersection and
PSPACE-complete for two smaller fragments; 3) $\Pi_{1}^{0}$-complete for ECoR*.
The second result gives PSPACE-upper bounds for some extensions of Kleene
algebra, including Kleene algebra with top w.r.t. binary relations.
