Fellows Logic Open Seminar

Equivalence in K-Variable Logics

This talk focuses on equivalence in finite variable logics, that is, whether two finite structures satisfy the same k-variable first-order sentences. I present an old open problem on the complexity of testing equivalence and discuss techniques to prove lower bounds via the corresponding k-pebble game.