Subshifts, MSO Logic, and Collapsing Hierarchies - Theoretical Computer Science
Conference Papers Year : 2014

Subshifts, MSO Logic, and Collapsing Hierarchies

Ilkka Törmä
  • Function : Author
  • PersonId : 994202

Abstract

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.
Fichier principal
Vignette du fichier
978-3-662-44602-7_10_Chapter.pdf (405.63 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01402035 , version 1 (24-11-2016)

Licence

Identifiers

Cite

Ilkka Törmä. Subshifts, MSO Logic, and Collapsing Hierarchies. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.111-122, ⟨10.1007/978-3-662-44602-7_10⟩. ⟨hal-01402035⟩
50 View
81 Download

Altmetric

Share

More