  We investigate the expressive power of first-order quantifications in the
context of monadic second-order logic over pictures. We show that k+1 set
quantifier alternations allow to define a picture language that cannot be
defined using k set quantifier alternations preceded by arbitrarily many
first-order quantifier alternations. The approach uses, for a given picture
language L and an integer m > 0 the height-m fragment of L, which is defined as
the word language obtained by considering each picture p of height m in L as a
word, where the letters of that word are the columns of p. A key idea is to
measure the complexity of a regular word language by the group complexity of
its syntactic monoid. Given a picture language L, such a word language measure
may be applied to each of its height fragments, so that the complexity of the
picture language is a function that maps each m to the complexity of the
height-m fragment of L. The asymptotic growth rate of that function may be
bounded based on the structure of a monadic second-order formula that defines
L. The core argument for that lower bound proof is based on Straubing's
algebraic characterization of the effect of first-order quantifiers on the
syntactic monoid of word languages by means of Rhodes' and Tilson's block
product.
