Finite Variable Logics in Descriptive Complexity Theory (Q4254565)

For \(k\geq 1\) let \(L^k\) be the ``finite variable logic'' consisting of all formulas of first-order logic containing at most \(k\) variables. For finite structures, these logics (as the infinitary variants and extensions by so-called counting quantifiers) have interesting model-theoretic, complexity-theoretic, and combinatorial aspects. The paper under review is a well-written and very comprehensive exposition of the state of the art of the theory. The author has contributed at a high level to a really wide variety of subjects of this theory. Central issues of the exposition are the complexity of equivalence testing and the complexity of computing canonical models for complete finite variable theories. There is a nice choice of insightful examples. This deep analysis and survey of the theory of finite variable logics closes pointing to areas of further research.