Undecidability of satisfiability in the algebra of finite binary relations with union, composition, and difference

Tony Tan, Jan Van den Bussche, Xiaowang Zhang

We consider expressions built up from binary relation names using the operators union, composition, and set difference. We show that it is undecidable to test whether a given such…