6533b7dcfe1ef96bd12734a9

RESEARCH PRODUCT

The Monadic Quantifier Alternation Hierarchy over Grids and Graphs

subject

description

AbstractThe monadic second-order quantifier alternation hierarchy over the class of finite graphs is shown to be strict. The proof is based on automata theoretic ideas and starts from a restricted class of graph-like structures, namely finite two-dimensional grids. Considering grids where the width is a function of the height, we prove that the difference between the levels k+1 and k of the monadic hierarchy is witnessed by a set of grids where this function is (k+1)-fold exponential. We then transfer the hierarchy result to the class of directed (or undirected) graphs, using an encoding technique called strong reduction. It is notable that one can obtain sets of graphs which occur arbitrarily high in the monadic hierarchy but are already definable in the first-order closure of existential monadic second-order logic. We also verify that these graph properties even belong to the complexity class NLOG, which indicates a profound difference between the monadic hierarchy and the polynomial hierarchy.