Category theory of symbolic dynamics. (English) Zbl 1314.37011
Summary: We study the central objects of symbolic dynamics, that is, subshifts and block maps, from the perspective of basic category theory, and present several natural categories with subshifts as objects and block maps as morphisms. Our main goals are to find universal objects in these symbolic categories, to classify their block maps based on their category theoretic properties, to prove category theoretic characterizations for notions arising from symbolic dynamics, and to establish as many natural properties (finite completeness, regularity etc.) as possible. Existing definitions in category theory suggest interesting new problems in symbolic dynamics. Our main technical contributions are the solution to the dual problem of the Extension Lemma and results on certain types of conserved quantities, suggested by the concept of a coequalizer.
MSC:
| 37B10 | Symbolic dynamics |
| 18B20 | Categories of machines, automata |
| 68Q45 | Formal languages and automata |
References:
| [1] | Boyle, M., Open problems in symbolic dynamics, (Geometric and Probabilistic Structures in Dynamics. Geometric and Probabilistic Structures in Dynamics, Contemp. Math., vol. 469 (2008), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 69-118 · Zbl 1158.37007 |
| [2] | Lind, D.; Marcus, B., An Introduction to Symbolic Dynamics and Coding (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1106.37301 |
| [3] | Boyle, M., Lower entropy factors of sofic systems, Ergodic Theory Dynam. Systems, 3, 4, 541-557 (1983) · Zbl 0529.28014 |
| [4] | Capobianco, S.; Uustalu, T., A categorical outlook on cellular automata, ArXiv e-prints |
| [5] | MacLane, S., Categories for the Working Mathematician, Graduate Texts in Mathematics, vol. 5 (1971), Springer-Verlag: Springer-Verlag New York · Zbl 0232.18001 |
| [6] | Johnstone, P. T., Sketches of an Elephant: A Topos Theory Compendium, vol. 1, Oxford Logic Guides, vol. 43 (2002), The Clarendon Press/Oxford University Press: The Clarendon Press/Oxford University Press New York · Zbl 1071.18001 |
| [7] | Johnstone, P. T., Sketches of an Elephant: A Topos Theory Compendium, vol. 2, Oxford Logic Guides, vol. 44 (2002), The Clarendon Press/Oxford University Press: The Clarendon Press/Oxford University Press Oxford · Zbl 1071.18001 |
| [8] | Carboni, A.; Lack, S.; Walters, R. F.C., Introduction to extensive and distributive categories, J. Pure Appl. Algebra, 84, 2, 145-158 (1993) · Zbl 0784.18001 |
| [9] | Thomsen, K., On the structure of a sofic shift space, Trans. Amer. Math. Soc., 356, 9, 3557-3619 (2004), (electronic) · Zbl 1260.37010 |
| [10] | Barth, J.; Dykstra, A., Weak equivalence for shifts of finite type, Indag. Math. (N.S.), 18, 4, 495-506 (2007) · Zbl 1143.37011 |
| [11] | Ceccherini-Silberstein, T.; Fiorenzi, F.; Scarabotti, F., The Garden of Eden theorem for cellular automata and for symbolic dynamical systems, (Random Walks and Geometry (2004), Walter de Gruyter: Walter de Gruyter Berlin), 73-108 · Zbl 1102.68080 |
| [12] | Kitchens, B. P., Symbolic Dynamics - One-Sided, Two-Sided and Countable State Markov Shifts, Universitext (1998), Springer-Verlag: Springer-Verlag Berlin · Zbl 0892.58020 |
| [13] | Krieger, W., On images of sofic systems, ArXiv e-prints |
| [14] | Hedlund, G. A., Endomorphisms and automorphisms of the shift dynamical system, Math. Syst. Theory, 3, 320-375 (1969) · Zbl 0182.56901 |
| [15] | Nešetřil, J., Ramsey theory, (Handbook of Combinatorics, vols. 1, 2 (1995), Elsevier: Elsevier Amsterdam), 1331-1403 · Zbl 0848.05065 |
| [16] | Taati, S., Cellular automata reversible over limit set, J. Cell. Autom., 2, 2, 167-177 (2007) · Zbl 1136.68438 |
| [17] | Boyle, M.; Kitchens, B.; Marcus, B., A note on minimal covers for sofic systems, Proc. Amer. Math. Soc., 95, 3, 403-411 (1985) · Zbl 0606.28016 |
| [18] | Lukkarila, V., Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata, J. Cell. Autom., 5, 3, 241-272 (2010) · Zbl 1203.68108 |
| [19] | Blanchard, F.; Tisseur, P., Some properties of cellular automata with equicontinuity points, Ann. Inst. Henri Poincaré Probab. Stat., 36, 5, 569-582 (2000) · Zbl 0964.37011 |
| [20] | Salo, V., A characterization of cellular automata generated by idempotents on the full shift, (Hirsch, E. A.; Karhumäki, J.; Lepistö, A.; Prilutskii, M., CSR. CSR, Lecture Notes in Computer Science, vol. 7353 (2012), Springer), 290-301 · Zbl 1360.68618 |
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.
