Multidimensional tilings and MSO logic
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915300910301184 |
|---|---|
| author | Pallen, Rémi Törmä, Ilkka |
| author_facet | Pallen, Rémi Törmä, Ilkka |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_17699 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multidimensional tilings and MSO logic Pallen, Rémi Törmä, Ilkka Formal Languages and Automata Theory Dynamical Systems Logic 03D55, 68Q15, 37B10, 37B51 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. |
| title | Multidimensional tilings and MSO logic |
| topic | Formal Languages and Automata Theory Dynamical Systems Logic 03D55, 68Q15, 37B10, 37B51 |
| url | https://arxiv.org/abs/2505.17699 |