Subshifts as models for MSO logic

Emmanuel Jeandel 1 Guillaume Theyssier 2
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We study the Monadic Second Order (MSO) Hierarchy over colourings of the discrete plane, and draw links between classes of formula and classes of subshifts. We give a characterization of existential MSO in terms of projections of tilings, and of universal sentences in terms of combinations of "pattern counting" subshifts. Conversely, we characterise logic fragments corresponding to various classes of subshifts (subshifts of finite type, sofic subshifts, all subshifts). Finally, we show by a separation result how the situation here is different from the case of tiling pictures studied earlier by Giammarresi et al.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2013, pp.1-15. 〈10.1016/j.ic.2013.01.003〉
Liste complète des métadonnées
Contributeur : Emmanuel Jeandel <>
Soumis le : jeudi 31 janvier 2013 - 14:17:13
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25

Lien texte intégral



Emmanuel Jeandel, Guillaume Theyssier. Subshifts as models for MSO logic. Information and Computation, Elsevier, 2013, pp.1-15. 〈10.1016/j.ic.2013.01.003〉. 〈hal-00783099〉



Consultations de la notice