MSO alternation hierarchy over pictures

Recomm. for undergrads: no
Posted by: dberwanger
on: May 18th, 2012

\begin{question} Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related. \end{question}

In [MST02], Matz, Schweikardt, and Thomas, proved that the MSO-alternation hierarchy is strict over the class of 2-dimensional rectangular pictures (and, as a consequence, is also strict over the class of finite graphs).

The proof of this hierarchy strictness is essentially based on the fact that, for any positive integer $k$, there is a function $f_k: \mathbb{N}\to \mathbb{N}$ (defined as a fixed height tower of exponentials) such that the set of rectangular grids of format $n\times f_k(n)$ (i.e, of width $n$ and length $f_k(n)$) can be defined by some $\Sigma_k$ MSO sentence but cannot be defined by some $\Sigma_{k-1}$ MSO sentence.

So, the hierarchy result essentially rests on the (more than exponential) imbalance between the two dimensions of the rectangular grid.

In view of this result a natural question is as follows. \begin{question} Is the MSO-alternation hierarchy strict for \emph{more well-balanced} pictures, for example, if it is required that the width and the length of the pictures are polynomially (resp. linearly) related? \end{question}

For example, for \emph{square} picture languages (or equivalently, rectangular picture languages for which the width and the length of the pictures are linearly related), the only thing we know is that EMSO (that is Existential or $\Sigma_1$ MSO) over square pictures is not closed under complement.

Oliver Matz (personal communication) thinks it is possible that any MSO sentence over square pictures be equivalent to a Boolean combination of existntial MSO sentences.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

[MST02] O. Matz, N. Schweikardt and W. Thomas, The Monadic Quantifier Alternation Hierarchy over Grids and Graphs, Information and Computation 179(2002), 356-383.

* indicates original appearance(s) of problem.