×

Subshifts, languages and logic. (English) Zbl 1247.03068

Diekert, Volker (ed.) et al., Developments in language theory. 13th international conference, DLT 2009, Stuttgart, Germany, June 30–July 3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02736-9/pbk). Lecture Notes in Computer Science 5583, 288-299 (2009).
Summary: 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, sofic subshifts).
For the entire collection see [Zbl 1165.68006].

MSC:

03D05 Automata and formal grammars in connection with logical questions
05B45 Combinatorial aspects of tessellation and tiling problems
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altenbernd, J.-H., Thomas, W., Wohrle, S.: Tiling systems over infinite pictures and their acceptance conditions. In: Developments in Language Theory (2003) · doi:10.1007/3-540-45005-X_26
[2] Ballier, A., Jeandel, E.: Tilings and model theory. In: First Symposium on Cellular Automata Journées Automates Cellulaires (2008)
[3] Berger, R.: The undecidability of the domino problem. Memoirs American Mathematical Society 66, 1966 (1966) · Zbl 0199.30802
[4] Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Springer Monographs in Mathematics. Springer, Berlin (1995) · Zbl 0841.03014
[5] Börger, Y.G.E., Grädel, E.: The classical decision problem. Springer, Telos (1996)
[6] Giammarresi, D., Restivo, A.: Two-Dimensional Languages. In: Handbook of Formal Languages, Beyond Words, vol. 3. Springer, Heidelberg (1997)
[7] 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 · doi:10.1006/inco.1996.0018
[8] Hanf, W.: Model-theoretic methods in the study of elementary logic. In: Symposium in the Theory of Models, pp. 132–145 (1965) · Zbl 0166.25801
[9] Harel, D.: Recurring Dominoes: Making the Highly Undecidable Highly Understandable. Annals of Discrete Mathematics 24, 51–72 (1985) · Zbl 0531.68003
[10] 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 · doi:10.1016/j.apal.2004.06.002
[11] Libkin, L.: Elements of Finite Model Theory. Texts in Theoretical Computer Science, an EATCS Series. Springer, Heidelberg (2004) · doi:10.1007/978-3-662-07003-1
[12] Makowsky, J.A.: On some conjectures connected with complete sentences. Fund. Math. 81, 193–202 (1974) · Zbl 0285.02042
[13] Matz, O., Schweikardt, N.: Expressive power of monadic logics on words, trees, pictures, and graphs. In: Gradel, E., Flum, J., Wilke, T. (eds.) Logic and Automata: History and Perspectives. Texts in Logic and Games, pp. 531–552. Amsterdam University Press (2007) · Zbl 1244.03118
[14] Oger, F.: Algebraic and model-theoretic properties of tilings. Theoretical computer science 319, 103–126 (2004) · Zbl 1047.52014 · doi:10.1016/j.tcs.2004.02.019
[15] Poizat, B.: Une théorie finiement axiomatisable et superstable. Groupe d’étude des théories stables 3(1), 1–9 (1980-1882)
[16] Robinson, R.M.: Undecidability and Nonperiodicity for Tilings of the Plane. Inventiones Math. 12 (1971) · Zbl 0197.46801 · doi:10.1007/BF01418780
[17] 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
[18] 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 · doi:10.1016/0168-0072(91)90054-P
[19] Thomas, W.: On logics, tilings, and automata. In: Leach Albert, J., Monien, B., Rodríguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol. 510, pp. 441–454. Springer, Heidelberg (1991) · Zbl 0769.68100 · doi:10.1007/3-540-54233-7_154
[20] Thomas, W.: Languages, Automata, and Logic. In: Thomas, W. (ed.) Handbook of Formal Languages, Beyond Words, vol. 3. Springer, Heidelberg (1997)
[21] Wang, H.: Proving theorems by pattern recognition ii. Bell system technical journal 40, 1–41 (1961) · doi:10.1002/j.1538-7305.1961.tb03975.x
[22] Weiss, B.: Subshifts of finite type and sofic systems. Monatshefte für Mathematik 77, 462–474 (1973) · Zbl 0285.28021 · doi:10.1007/BF01295322
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.