Skip to Main content Skip to Navigation
Conference papers

Subshifts, MSO Logic, and Collapsing Hierarchies

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01402035
Contributor : Hal Ifip <>
Submitted on : Thursday, November 24, 2016 - 10:49:22 AM
Last modification on : Thursday, November 24, 2016 - 11:14:11 AM
Long-term archiving on: : Tuesday, March 21, 2017 - 10:39:39 AM

File

978-3-662-44602-7_10_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

92

Files downloads

165