• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Subshifts, MSO Logic, and Collapsing Hierarchies

Ilkka Törmä, Subshifts, MSO Logic, and Collapsing Hierarchies. In: Josep Diaz, Ivan Lanese, Davide Sangiorgi (Eds.), Theoretical Computer Science, Lecture Notes in Computer Science 8705, 111–122, Springer, 2014.

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

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.

BibTeX entry:

@INPROCEEDINGS{inpTorma_Ilkka14a,
  title = {Subshifts, MSO Logic, and Collapsing Hierarchies},
  booktitle = {Theoretical Computer Science},
  author = {Törmä, Ilkka},
  volume = {8705},
  series = {Lecture Notes in Computer Science},
  editor = {Diaz, Josep and Lanese, Ivan and Sangiorgi, Davide},
  publisher = {Springer},
  pages = {111–122},
  year = {2014},
  keywords = {subshift, MSO logic, quantifier alternation},
  ISSN = {0302-9743},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication