Skip to Main content Skip to Navigation
Journal articles

Subshifts as models for MSO logic

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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-00783099
Contributor : Emmanuel Jeandel <>
Submitted on : Thursday, January 31, 2013 - 2:17:13 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM

Links full text

Identifiers

Citation

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⟩

Share

Metrics

Record views

322