Subshifts and Logic: Back and Forth

Details Subshifts and Logic: Back and Forth Subshifts and Logic: Back and Forth

2009-12-07

arxiv.org/abs/0912.1272v1

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Subshifts and Logic: Back and Forth does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Subshifts and Logic: Back and Forth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subshifts and Logic: Back and Forth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-243573