A4 Refereed article in a conference publication
Multidimensional Tilings and MSO Logic
Authors: Pallen, Rémi; Törmä, Ilkka
Editors: Beckmann, Arnold; Oitavem, Isabel; Manea, Florin
Conference name: Computability in Europe
Publisher: Springer Nature Switzerland
Publication year: 2025
Journal: Lecture Notes in Computer Science
Book title : Crossroads of Computability and Logic: Insights, Inspirations, and Innovations: 21st Conference on Computability in Europe, CiE 2025, Lisbon, Portugal, July 14–18, 2025, Proceedings
Journal name in source: Lecture Notes in Computer Science
Volume: 15764
First page : 365
Last page: 379
ISBN: 978-3-031-95907-3
eISBN: 978-3-031-95908-0
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-031-95908-0_26
Web address : https://doi.org/10.1007/978-3-031-95908-0_26
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.
Funding information in the publication:
Ilkka Törmä was supported by the Academy of Finland grant 359921.
