Multidimensional tilings and MSO logic

2025/05/23 by Pallen, Rémi, Törmä, Ilkka
#03D55 #37B10 #37B51 #68Q15 #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO)

paper · doi:10.48550/arxiv.2505.17699

Abstract

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.

Citations

• Diddy: a Python toolbox for infinite discrete dynamical systems
• Subshifts, MSO Logic, and Collapsing Hierarchies
• Subshifts as Models for MSO Logic
• The undecidability of the domino problem

Related

• Subshifts as Models for MSO Logic
• Subshifts, MSO Logic, and Collapsing Hierarchies
• The MSO+U theory of (N, <) is undecidable
• MSO logic of the real order with the set quantifiers ranging over the Borel sets
• Tiling problems and complexity of logics (extended version)