A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Subshifts, MSO Logic, and Collapsing Hierarchies
Tekijät: Ilkka Törmä
Toimittaja: Josep Diaz, Ivan Lanese, Davide Sangiorgi
Konferenssin vakiintunut nimi: IFIP international conference on theoretical computer science
Kustannuspaikka: Berlin
Julkaisuvuosi: 2014
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Theoretical Computer Science
Sarjan nimi: Lecture Notes in Computer Science
Numero sarjassa: 8705
Vuosikerta: 1
Aloitussivu: 111
Lopetussivu: 122
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-662-44602-7_10
Verkko-osoite: 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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
