zbMATH — the first resource for mathematics

Subshifts as models for MSO logic. (English) Zbl 1435.03064
Summary: We study the Monadic Second Order (MSO) Hierarchy over colorings 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 characterize 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.

03C90 Nonclassical models (Boolean-valued, sheaf, etc.)
03B16 Higher-order logic
37B10 Symbolic dynamics
Full Text: DOI
[1] Thomas, W., Languages, automata, and logic, (Handbook of Formal Languages, Vol. 3. Beyond Words, (1997), Springer)
[2] Matz, O.; Schweikardt, N., Expressive power of monadic logics on words, trees, pictures, and graphs, (Flum, E. G.J.; Wilke, T., Logic and Automata: History and Perspectives, Texts in Logic and Games, (2007), Amsterdam University Press), 531-552 · Zbl 1244.03118
[3] Delacourt, M., Riceʼs theorem for μ-limit sets of cellular automata, (Automata, Languages and Programming, ICALP 2011, Lecture Notes in Computer Science, vol. 6756, (2011), Springer), 89-100 · Zbl 1334.68141
[4] L. Boyer, G. Theyssier, On factor universality in symbolic spaces, in: MFCS, 2010, pp. 209-220. · Zbl 1287.68115
[5] L. Boyer, G. Theyssier, On local symmetries and universality in cellular automata, in: STACS, 2009, pp. 195-206. · Zbl 1236.68187
[6] G. Lafitte, M. Weiss, Universal tilings, in: STACS, 2007, pp. 367-380.
[7] G. Lafitte, M. Weiss, Computability of tilings, in: IFIP TCS, 2008, pp. 187-201.
[8] D. Doty, M.J. Patitz, D. Reishus, R.T. Schweller, S.M. Summers, Strong fault-tolerance for self-assembly with fuzzy temperature, in: FOCS, 2010, pp. 417-426.
[9] D. Doty, J.H. Lutz, M.J. Patitz, S.M. Summers, D. Woods, Intrinsic universality in self-assembly, in: STACS, 2010, pp. 275-286. · Zbl 1230.68071
[10] Wang, H., Proving theorems by pattern recognition II, Bell System Technical Journal, 40, 1-41, (1961)
[11] Berger, R., The undecidability of the domino problem, Memoirs American Mathematical Society, 66, 1966, (1966) · Zbl 0199.30802
[12] Börger, E.; Grädel, E.; Gurevich, Y., The classical decision problem, (1996), Springer-Verlag Telos
[13] Kuske, D.; Lohrey, M., Logical aspects of Cayley-graphs: the group case, Annals of Pure and Applied Logic, 131, 1-3, 263-286, (2005) · Zbl 1063.03005
[14] Seese, D., The structure of the models of decidable monadic theories of graphs, Annals of Pure and Applied Logic, 53, 2, 169-195, (1991) · Zbl 0733.03026
[15] Makowsky, J., On some conjectures connected with complete sentences, Fundamenta Mathematicae, 81, 193-202, (1974) · Zbl 0285.02042
[16] Poizat, B., Une théorie finiement axiomatisable et superstable, Groupe Dʼétude des Théories Stables, 3, 1, 1-9, (1980-1982) · Zbl 0539.03012
[17] Robinson, R. M., Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 12, 177-209, (1971) · Zbl 0197.46801
[18] Oger, F., Algebraic and model-theoretic properties of tilings, Theoretical Computer Science, 319, 103-126, (2004) · Zbl 1047.52014
[19] A. Ballier, E. Jeandel, Tilings and model theory, First Symposium on Cellular Automata, Journées Automates Cellulaires.
[20] Giammarresi, D.; Restivo, A., Two-dimensional languages, (Handbook of Formal Languages, Vol. 3. Beyond Words, (1997), Springer)
[21] Giammarresi, D.; Restivo, A.; Seibert, S.; Thomas, W., Monadic second-order logic over rectangular pictures and recognizability by tiling systems, Information and Computation, 125, 32-45, (1996) · Zbl 0853.68131
[22] Weiss, B., Subshifts of finite type and sofic systems, Monatshefte für Mathematik, 77, 462-474, (1973) · Zbl 0285.28021
[23] M. Anselmo, N. Jonoska, M. Madonia, Framed versus unframed two-dimensional languages, in: 35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM, 2009, pp. 79-92. · Zbl 1206.68166
[24] J.-H. Altenbernd, W. Thomas, S. Wohrle, Tiling systems over infinite pictures and their acceptance conditions, in: Developments in Language Theory, 2003. · Zbl 1015.68117
[25] Harel, D., Recurring dominoes: making the highly undecidable highly understandable, Annals of Discrete Mathematics, 24, 51-72, (1985) · Zbl 0531.68003
[26] Jeandel, E.; Theyssier, G., Subshifts, languages and logic, (Developments in Language Theory (DLT), Lecture Notes in Computer Science, vol. 5583, (2009), Springer), 288-299 · Zbl 1247.03068
[27] W. Hanf, Model-theoretic methods in the study of elementary logic, in: Symposium in the Theory of Models, 1965, pp. 132-145. · Zbl 0166.25801
[28] Ebbinghaus, H.-D.; Flum, J., Finite model theory, Springer Monographs in Mathematics, (1995), Springer Berlin · Zbl 0841.03014
[29] Libkin, L., Elements of finite model theory, Texts in Theoretical Computer Science, an EATCS Series, (2004), Springer-Verlag · Zbl 1060.03002
[30] Thomas, W., On logics, tilings, and automata, (Berlin, S., Proceedings of the 18th ICALP, Lecture Notes in Computer Science, vol. 510, (1991)), 441-454 · Zbl 0769.68100
[31] Schwentick, T.; Barthelmann, K., Local normal forms for first-order logic with applications to games and automata, Discrete Mathematics and Theoretical Computer Science, 3, 109-124, (1999) · Zbl 0935.03015
[32] Lind, D.; Marcus, B., An introduction to symbolic dynamics and coding, (1995), Cambridge University Press · Zbl 1106.37301
[33] Grohe, M.; Wöhrle, S., An existential locality theorem, Annals of Pure and Applied Logic, 129, 1-3, 131-148, (2004) · Zbl 1056.03017
[34] Beauquier, D.; Pin, J.-E., Languages and scanners, Theoretical Computer Science, 84, 3-21, (1991) · Zbl 0753.68054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.