An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations

Yuya Uezato

Three-variable first-order logic (FO3) and the calculus of relations (CoR) define the same binary queries, an equivalence going back to Tarski in the 1940s. While the classical tra…