Subshifts, MSO Logic, and Collapsing Hierarchies




Ilkka Törmä

Josep Diaz, Ivan Lanese, Davide Sangiorgi

IFIP international conference on theoretical computer science

Berlin

2014

Lecture Notes in Computer Science

Theoretical Computer Science

Lecture Notes in Computer Science

8705

1

111

122

0302-9743

DOIhttps://doi.org/10.1007/978-3-662-44602-7_10

http://link.springer.com/chapter/10.1007/978-3-662-44602-7_10



We use monadic second-order logic to define two-dimensional subshifts, or sets of colorings of the infinite plane. We present a natural family of quantifier alternation hierarchies, and show that they all collapse to the third level. In particular, this solves an open problem of [Jeandel & Theyssier 2013]. The results are in stark contrast with picture languages, where such hierarchies are usually infinite.



Last updated on 2024-26-11 at 12:34