The Monadic Quantifier Alternation Hierarchy over Graphs is Infinite

We show that the monadic second-order quantifier alternation hierarchy over finite directed graphs and over finite two-dimensional grids is infinite. For this purpose we investigate sets of grids where the width is a function in the height. The infiniteness of the hierarchy is then witnessed by n-fold exponential functions for increasing integers n. 1 Introduction The subject of this paper is monadic second-order logic over graphs. In this logic, one can quantify over vertices and sets of vertices; typical properties which are formalizable in monadic logic are 3-colourability and connectivity. (A graph is 3-colourable if there are three disjoint vertex sets which cover the graph and define a colouring; a graph is not connected iff there are two vertex sets which define a nontrivial partition such that no edge leads from one set to the other.) Monadic second-order graph properties can be classified by the alternation depth of set quantifiers which occur in defining formulas. One speaks..