A4 Refereed article in a conference publication

Subshifts, MSO Logic, and Collapsing Hierarchies



Authors: Ilkka Törmä

Editors: Josep Diaz, Ivan Lanese, Davide Sangiorgi

Conference name: IFIP international conference on theoretical computer science

Publishing place: Berlin

Publication year: 2014

Journal: Lecture Notes in Computer Science

Book title : Theoretical Computer Science

Series title: Lecture Notes in Computer Science

Number in series: 8705

Volume: 1

First page : 111

Last page: 122

ISSN: 0302-9743

DOI: https://doi.org/10.1007/978-3-662-44602-7_10(external)

Web address : http://link.springer.com/chapter/10.1007/978-3-662-44602-7_10(external)


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.



Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.


Last updated on 2024-26-11 at 12:34