One Quantifier Will Do in Existential Monadic Second-Order Logic over Pictures

. We show that every formula of the existential fragment of monadic second-order logic over picture models (i.e., finite, two-dimensional, coloured grids) is equivalent to one with only one existential monadic quantifier. The corresponding claim is true for the class of word models ([Tho82]) but not for the class of graphs ([Ott95]). The class of picture models is of particular interest because it has been used to show the strictness of the different (and more popular) hierarchy of quantifier alternation. 1 Introduction We study monadic second-order logic (MSO) over finite structures. For a given class of structures, one can consider the following two hierarchies: 1. the quantifier alternation hierarchy, where properties are classified wrt. the number of monadic quantifier alternations required for an MSO-sentence; 2. the existential-quantifier depth hierarchy, where properties in the existential fragment of monadic second-order logic (i.e., on the lowest level of the alternation hier..