Multidimensional tilings and MSO logic
arXiv:2505.17699
Abstract
We define sets of coulourings of the infinite discrete plane using monadic second order (MSO) formulas. We determine the complexity of deciding whether such a formula defines a subshift, parametrized on the quantifier alternation complexity of the formula. We also study the complexities of languages of MSO-definable sets, giving either an exact classification or upper and lower bounds for each quantifier alternation class.
15+11 pages, 4+2 figures. To be presented at Computability in Europe 2025