Multidimensional Tilings and MSO Logic

Pallen, Rémi; Törmä, Ilkka
Multidimensional Tilings and MSO Logic

Pallen, Rémi
Törmä, Ilkka

Tätä artikkelia/julkaisua ei ole tallennettu UTUPubiin. Julkaisun tiedoissa voi kuitenkin olla linkki toisaalle tallennettuun artikkeliin / julkaisuun.

doi:10.1007/978-3-031-95908-0_26
URI
https://doi.org/10.1007/978-3-031-95908-0_26
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe202601215915
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.
Kokoelmat