A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Multidimensional Tilings and MSO Logic
Tekijät: Pallen, Rémi; Törmä, Ilkka
Toimittaja: Beckmann, Arnold; Oitavem, Isabel; Manea, Florin
Konferenssin vakiintunut nimi: Computability in Europe
Kustantaja: Springer Nature Switzerland
Julkaisuvuosi: 2025
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Crossroads of Computability and Logic: Insights, Inspirations, and Innovations: 21st Conference on Computability in Europe, CiE 2025, Lisbon, Portugal, July 14–18, 2025, Proceedings
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science
Vuosikerta: 15764
Aloitussivu: 365
Lopetussivu: 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
Verkko-osoite: 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.
Julkaisussa olevat rahoitustiedot:
Ilkka Törmä was supported by the Academy of Finland grant 359921.
