%0 Conference Proceedings
%T Subshifts, MSO Logic, and Collapsing Hierarchies
%+ University of Turku
%A Törmä, Ilkka
%Z Part 1: Track A: Algorithms, Complexity and Models of Computation
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 8th IFIP International Conference on Theoretical Computer Science (TCS)
%C Rome, Italy
%Y Josep Diaz
%Y Ivan Lanese
%Y Davide Sangiorgi
%I Springer
%3 Theoretical Computer Science
%V LNCS-8705
%P 111-122
%8 2014-09-01
%D 2014
%R 10.1007/978-3-662-44602-7_10
%K subshift
%K MSO logic
%K quantifier alternation
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z TC 2
%Z WG 2.2
%2 https://inria.hal.science/hal-01402035/document
%2 https://inria.hal.science/hal-01402035/file/978-3-662-44602-7_10_Chapter.pdf
%L hal-01402035
%U https://inria.hal.science/hal-01402035
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC2
%~ IFIP-LNCS-8705
%~ IFIP-TCS
%~ IFIP-WG2-2