Constructions with Countable Subshifts of Finite Type

• Autorzy: Salo V. , Törmä I.
• Języki publikacji: EN

Abstrakty

EN

We present constructions of countable two-dimensional subshifts of finite type (SFTs) with interesting properties. Our main focus is on properties of the topological derivatives and subpattern posets of these objects. We present a countable SFT whose iterated derivatives are maximally complex from the computational point of view, constructions of countable SFTs with high Cantor-Bendixson ranks, a countable SFT whose subpattern poset contains an infinite descending chain and a countable SFT whose subpattern poset contains all finite posets. When possible, we make these constructions deterministic, and ensure the sets of rows are very simple as one-dimensional subshifts.

Słowa kluczowe

EN

Cantor-Bendixson rank; countable subshifts; subpattern poset

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 126, nr 2-3
• Strony: 263--300
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Salo V.

• TUCS – Turku Centre for Computer Science, Finland
• University of Turku, Finland

autor

Törmä I.

• TUCS – Turku Centre for Computer Science, Finland
• University of Turku, Finland

Bibliografia

• [1] Ballier, A., Durand, B., Jeandel, E.: Structural aspects of tilings, Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science (P. W. Susanne Albers, Ed.), IBFI Schloss Dagstuhl, Bordeaux, France, February 2008, 11 pages.
• [2] Berger, R.: The undecidability of the domino problem, Mem. Amer. Math. Soc. No., 66, 1966, ISSN 00659266, 72 pages.
• [3] Boyle, M., Lind, D.: Expansive Subdynamics, 1997.
• [4] Cenzer, D., Clote, P., Smith, R. L., Soare, R. I., Wainer, S. S.: Members of countable n0 classes, Ann. Pure Appl. Logic, 31(2-3), 1986, 145-163, ISSN 0168-0072, Special issue: second Southeast Asian logic conference (Bangkok, 1984).
• [5] Cenzer, D., Dashti, A., Toska, F., Wyman, S.: Computability of Countable Subshifts in One Dimension, Theory of Computing Systems, 51(3), 2012, 352-371, ISSN 1432-4350.
• [6] Cenzer, D., Remmel, J. B.: n0 classes in mathematics, in: Handbook of recursive mathematics, Vol. 2, vol. 139 of Stud. Logic Found. Math., North-Holland, Amsterdam, 1998, 623-821.
• [7] Dennunzio, A., Formenti, E., Weiss, M.: Multidimensional Cellular Automata: closing property, quasiexpansivity and (un)decidability issues., 2013, Submitted to Theoretical Computer Science.
• [8] Durand, B., Romashchenko, A., Shen, A.: Fixed-point tile sets and their applications, J. Comput. System Sci., 78(3), 2012, 731-764, ISSN 0022-0000.
• [9] Fine, N. J., Wilf, H. S.: Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc., 16, 1965, 109-114, ISSN 0002-9939.
• [10] Hedlund, G. A.: Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory, 3, 1969, 320-375, ISSN 0025-5661.
• [11] Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176(1), 2009, 131-167, ISSN 0020-9910.
• [12] Jeandel, E., Vanier, P.: n0 sets and tilings, Theory and Applications of Models of Computation (TAMC), 6648, 2011.
• [13] Kari, J.: A small aperiodic set of Wang tiles, Discrete Math., 160(1-3), 1996, 259-264, ISSN 0012-365X.
• [14] Kreisel, G., Shoenfield, J., Wang, H.: Number theoretic concepts and recursive well-orderings, Arch. Math. Logik Grundlagenforsch., 5, 1960, 42-64, ISSN 0003-9268.
• [15] Lind, D., Marcus, B.: An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995, ISBN 0-521-55124-2; 0-521-55900-6.
• [16] Minsky, M. L.: Computation: finite and infinite machines, Prentice-Hall Inc., Englewood Cliffs, N.J., 1967, Prentice-Hall Series in Automatic Computation.
• [17] Morita, K.: Universality of a reversible two-counter machine, Theoretical Computer Science, 1996.
• [18] Odifreddi, P.: Classical recursion theory, vol. 125 of Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1989, ISBN 0-444-87295-7, The theory of functions and sets of natural numbers, With a foreword by G. E. Sacks.
• [19] Pavlov, R., Schraudner, M.: Classification of sofic proj ective subdynamics of multidimensional shifts of finite type, Submitted.
• [20] Robinson, R. M.: Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12, 1971, 177209, ISSN 0020-9910.
• [21] Salo, V, Torma, I.: Computational Aspects of Cellular Automata on Countable Sofic Shifts, Mathematical Foundations of Computer Science 2012, 2012, 777-788.
• [22] Salo, V., Torma, I.: On Derivatives and Subpattern Orders of Countable Subshifts, ArXiv e-prints, August 2012.