Multidimensional Tilings and MSO Logic
Tässä tietueessa ei ole tiedostoja, ainoastaan metadata.
Pysyvä osoite
Verkkojulkaisu
Tiivistelmä
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.