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.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.111-122, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_10〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402035
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:49:22
Dernière modification le : jeudi 24 novembre 2016 - 11:14:11
Document(s) archivé(s) le : mardi 21 mars 2017 - 10:39:39

Fichier

978-3-662-44602-7_10_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Ilkka Törmä. Subshifts, MSO Logic, and Collapsing Hierarchies. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.111-122, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_10〉. 〈hal-01402035〉

Partager

Métriques

Consultations de la notice

26

Téléchargements de fichiers

9