Multidimensional Tilings and MSO Logic

: Pallen, Rémi; Törmä, Ilkka

: Beckmann, Arnold; Oitavem, Isabel; Manea, Florin

: Computability in Europe

Publisher: Springer Nature Switzerland

: 2025

: Lecture Notes in Computer Science

: Crossroads of Computability and Logic: Insights, Inspirations, and Innovations: 21st Conference on Computability in Europe, CiE 2025, Lisbon, Portugal, July 14–18, 2025, Proceedings

: Lecture Notes in Computer Science

: 15764

: 365

: 379

: 978-3-031-95907-3

: 978-3-031-95908-0

: 0302-9743

: 1611-3349

DOI: https://doi.org/10.1007/978-3-031-95908-0_26

: https://doi.org/10.1007/978-3-031-95908-0_26

: https://research.utu.fi/converis/portal/detail/Publication/499418099

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.

:
Ilkka Törmä was supported by the Academy of Finland grant 359921.