Subshifts, MSO Logic, and Collapsing Hierarchies - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Subshifts, MSO Logic, and Collapsing Hierarchies

Ilkka Törmä
  • Fonction : Auteur
  • PersonId : 994202

Résumé

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.
Fichier principal
Vignette du fichier
978-3-662-44602-7_10_Chapter.pdf (405.63 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01402035 , version 1 (24-11-2016)

Licence

Paternité

Identifiants

Citer

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⟩
29 Consultations
65 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More