Subshifts, Languages and Logic
classification
💻 cs.DM
cs.LO
keywords
subshiftstilingsinfinitelogicpicturescharacterisecharacterizationclasses
read the original abstract
We study the Monadic Second Order (MSO) Hierarchy over infinite pictures, that is tilings. We give a characterization of existential MSO in terms of tilings and projections of tilings. Conversely, we characterise logic fragments corresponding to various classes of infinite pictures (subshifts of finite type, so?c subshifts).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.