# American Institute of Mathematical Sciences

December  2011, 15(3): 739-767. doi: 10.3934/dcdsb.2011.15.739

## Computation of symbolic dynamics for two-dimensional piecewise-affine maps

 1 Niels Bohrweg 1, Leiden, 2333 CA, Netherlands 2 Bouillonstraat 8-10, 6211 LH Maastricht, Netherlands

Received  June 2009 Revised  June 2010 Published  February 2011

In this paper we design and implement an algorithm for computing symbolic dynamics for two dimensional piecewise-affine maps. The algorithm is based on detection of periodic orbits using the Conley index and Szymczak decomposition of Conley index pair. The algorithm is also extended to deal with discontinuous maps. We compare the algorithm with the algorithm based on tangle of fixed points. We apply the algorithms to compute the symbolic dynamics and entropy bounds for the Lozi map.
Citation: Lorenzo Sella, Pieter Collins. Computation of symbolic dynamics for two-dimensional piecewise-affine maps. Discrete and Continuous Dynamical Systems - B, 2011, 15 (3) : 739-767. doi: 10.3934/dcdsb.2011.15.739
##### References:
 [1] D. Lind and B. Marcus, "An Introduction To Symbolic Dynamics And Coding," Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511626302. [2] J. Milnor and W. Thurston, On iterated maps of the interval, in "Dynamical Systems" (College Park, MD, 1986-87), 465-563, Lecture Notes in Math, Springer, 1342, Berlin, 1988. [3] J. P. Lampreia and S. Ramos, Trimodal maps, International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 3 (1993), 1607-1617. doi: 10.1142/S0218127493001276. [4] J. P. Lampreia and S. Ramos, Kneading theory for tree maps, Ergodic Theory and Dynamical Systems, 24 (2004), 957-985. doi: 10.1017/S014338570400015X. [5] J. L. Rocha and S. Ramos, On iterated maps of the interval with holes, Journal of Difference Equations and Applications, 9 (2003), 319-335. doi: 10.1080/1023619021000047752. [6] L. Sella and P. Collins, "Discrete Dynamics of Two-Dimensional Nonlinear Hybrid Automata," Hybrid Systems: Computation and Control, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2008. [7] P. Collins, Symbolic dynamics from homoclinic tangles, HInternational Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 12 (2002), 605-617. doi: 10.1142/S0218127402004565. [8] T. Kaczynski, K. Mischaikow and M. Mrozek, "Computational Homology," Applied Mathematical Sciences, 157, Springer-Verlag, New York. [9] S. Day, O. Junge and M. Konstantin, Towards automated chaos verification, EQUADIFF, 2003, 157-162, World Sci. Publ., Hackensack, NJ, 2005. [10] Z. Galias and P. Zgliczyński, Abundance of homoclinic and heteroclinic orbits and rigorous bounds for the topological entropy for the Hénon map, Nonlinearity, 14 (2001), 909-932. doi: 10.1088/0951-7715/14/5/301. [11] A. Szymczak, The Conley index for decompositions of isolated invariant sets, Fundamenta Mathematicae, 148 (1995), 71-90. [12] P. Collins, Dynamics of surface diffeomorphisms relative to homoclinic and heteroclinic orbits, Dynamical Systems, 19 (2004), 1-39. doi: 10.1080/14689360310001623421. [13] M. Misiurewicz, Strange attractors for the Lozi mappings, Nonlinear Dynamics (Internat. Conf., New York, 1979)), 348-358, Ann. New York Acad. Sci., 357, New York Acad. Sci., New York, 1980. [14] A. Hatcher, "Algebraic Topology," Cambridge University Press, Cambridge, 2002. [15] J. Munkres, "Elements of Algebraic Topology," Addison-Wesley Publishing Company, New York, 2002. [16] R. Gilmore and M. Lefranc, "The Topology of Chaos," Alice in Stretch and Squeezeland, Wiley-Interscience [John Wiley & Sons], Menlo Park, CA, 1984. [17] D. Sand, Numerical computations on Lozi maps, http://topo.math.u-psud.fr/ sands/Programs/Lozi/index.html.

show all references

##### References:
 [1] D. Lind and B. Marcus, "An Introduction To Symbolic Dynamics And Coding," Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511626302. [2] J. Milnor and W. Thurston, On iterated maps of the interval, in "Dynamical Systems" (College Park, MD, 1986-87), 465-563, Lecture Notes in Math, Springer, 1342, Berlin, 1988. [3] J. P. Lampreia and S. Ramos, Trimodal maps, International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 3 (1993), 1607-1617. doi: 10.1142/S0218127493001276. [4] J. P. Lampreia and S. Ramos, Kneading theory for tree maps, Ergodic Theory and Dynamical Systems, 24 (2004), 957-985. doi: 10.1017/S014338570400015X. [5] J. L. Rocha and S. Ramos, On iterated maps of the interval with holes, Journal of Difference Equations and Applications, 9 (2003), 319-335. doi: 10.1080/1023619021000047752. [6] L. Sella and P. Collins, "Discrete Dynamics of Two-Dimensional Nonlinear Hybrid Automata," Hybrid Systems: Computation and Control, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2008. [7] P. Collins, Symbolic dynamics from homoclinic tangles, HInternational Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 12 (2002), 605-617. doi: 10.1142/S0218127402004565. [8] T. Kaczynski, K. Mischaikow and M. Mrozek, "Computational Homology," Applied Mathematical Sciences, 157, Springer-Verlag, New York. [9] S. Day, O. Junge and M. Konstantin, Towards automated chaos verification, EQUADIFF, 2003, 157-162, World Sci. Publ., Hackensack, NJ, 2005. [10] Z. Galias and P. Zgliczyński, Abundance of homoclinic and heteroclinic orbits and rigorous bounds for the topological entropy for the Hénon map, Nonlinearity, 14 (2001), 909-932. doi: 10.1088/0951-7715/14/5/301. [11] A. Szymczak, The Conley index for decompositions of isolated invariant sets, Fundamenta Mathematicae, 148 (1995), 71-90. [12] P. Collins, Dynamics of surface diffeomorphisms relative to homoclinic and heteroclinic orbits, Dynamical Systems, 19 (2004), 1-39. doi: 10.1080/14689360310001623421. [13] M. Misiurewicz, Strange attractors for the Lozi mappings, Nonlinear Dynamics (Internat. Conf., New York, 1979)), 348-358, Ann. New York Acad. Sci., 357, New York Acad. Sci., New York, 1980. [14] A. Hatcher, "Algebraic Topology," Cambridge University Press, Cambridge, 2002. [15] J. Munkres, "Elements of Algebraic Topology," Addison-Wesley Publishing Company, New York, 2002. [16] R. Gilmore and M. Lefranc, "The Topology of Chaos," Alice in Stretch and Squeezeland, Wiley-Interscience [John Wiley & Sons], Menlo Park, CA, 1984. [17] D. Sand, Numerical computations on Lozi maps, http://topo.math.u-psud.fr/ sands/Programs/Lozi/index.html.
 [1] Anke D. Pohl. Symbolic dynamics for the geodesic flow on two-dimensional hyperbolic good orbifolds. Discrete and Continuous Dynamical Systems, 2014, 34 (5) : 2173-2241. doi: 10.3934/dcds.2014.34.2173 [2] Tiantian Wu, Xiao-Song Yang. A new class of 3-dimensional piecewise affine systems with homoclinic orbits. Discrete and Continuous Dynamical Systems, 2016, 36 (9) : 5119-5129. doi: 10.3934/dcds.2016022 [3] Anatoli F. Ivanov. On global dynamics in a multi-dimensional discrete map. Conference Publications, 2015, 2015 (special) : 652-659. doi: 10.3934/proc.2015.0652 [4] Jiaxi Huang, Youde Wang, Lifeng Zhao. Equivariant Schrödinger map flow on two dimensional hyperbolic space. Discrete and Continuous Dynamical Systems, 2020, 40 (7) : 4379-4425. doi: 10.3934/dcds.2020184 [5] Sebastián Ferrer, Francisco Crespo. Alternative angle-based approach to the $\mathcal{KS}$-Map. An interpretation through symmetry and reduction. Journal of Geometric Mechanics, 2018, 10 (3) : 359-372. doi: 10.3934/jgm.2018013 [6] Simone Creo, Maria Rosaria Lancia, Alexander Nazarov, Paola Vernole. On two-dimensional nonlocal Venttsel' problems in piecewise smooth domains. Discrete and Continuous Dynamical Systems - S, 2019, 12 (1) : 57-64. doi: 10.3934/dcdss.2019004 [7] Wolf-Jürgen Beyn, Thorsten Hüls. Continuation and collapse of homoclinic tangles. Journal of Computational Dynamics, 2014, 1 (1) : 71-109. doi: 10.3934/jcd.2014.1.71 [8] Ketty A. De Rezende, Mariana G. Villapouca. Discrete conley index theory for zero dimensional basic sets. Discrete and Continuous Dynamical Systems, 2017, 37 (3) : 1359-1387. doi: 10.3934/dcds.2017056 [9] David Burguet. Examples of $\mathcal{C}^r$ interval map with large symbolic extension entropy. Discrete and Continuous Dynamical Systems, 2010, 26 (3) : 873-899. doi: 10.3934/dcds.2010.26.873 [10] Boris Kruglikov, Martin Rypdal. A piece-wise affine contracting map with positive entropy. Discrete and Continuous Dynamical Systems, 2006, 16 (2) : 393-394. doi: 10.3934/dcds.2006.16.393 [11] Luigi Ambrosio, Federico Glaudo, Dario Trevisan. On the optimal map in the $2$-dimensional random matching problem. Discrete and Continuous Dynamical Systems, 2019, 39 (12) : 7291-7308. doi: 10.3934/dcds.2019304 [12] Hun Ki Baek, Younghae Do. Dangerous Border-Collision bifurcations of a piecewise-smooth map. Communications on Pure and Applied Analysis, 2006, 5 (3) : 493-503. doi: 10.3934/cpaa.2006.5.493 [13] Zhiying Qin, Jichen Yang, Soumitro Banerjee, Guirong Jiang. Border-collision bifurcations in a generalized piecewise linear-power map. Discrete and Continuous Dynamical Systems - B, 2011, 16 (2) : 547-567. doi: 10.3934/dcdsb.2011.16.547 [14] Micah Webster, Patrick Guidotti. Boundary dynamics of a two-dimensional diffusive free boundary problem. Discrete and Continuous Dynamical Systems, 2010, 26 (2) : 713-736. doi: 10.3934/dcds.2010.26.713 [15] Tony Wong, Michael J. Ward. Dynamics of patchy vegetation patterns in the two-dimensional generalized Klausmeier model. Discrete and Continuous Dynamical Systems - S, 2022, 15 (9) : 2747-2793. doi: 10.3934/dcdss.2022043 [16] Antonio Pumariño, José Ángel Rodríguez, Enrique Vigil. Renormalization of two-dimensional piecewise linear maps: Abundance of 2-D strange attractors. Discrete and Continuous Dynamical Systems, 2018, 38 (2) : 941-966. doi: 10.3934/dcds.2018040 [17] Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487 [18] Ming Zhao, Cuiping Li, Jinliang Wang, Zhaosheng Feng. Bifurcation analysis of the three-dimensional Hénon map. Discrete and Continuous Dynamical Systems - S, 2017, 10 (3) : 625-645. doi: 10.3934/dcdss.2017031 [19] Dyi-Shing Ou, Kenneth James Palmer. A constructive proof of the existence of a semi-conjugacy for a one dimensional map. Discrete and Continuous Dynamical Systems - B, 2012, 17 (3) : 977-992. doi: 10.3934/dcdsb.2012.17.977 [20] Steven M. Pederson. Non-turning Poincaré map and homoclinic tangencies in interval maps with non-constant topological entropy. Conference Publications, 2001, 2001 (Special) : 295-302. doi: 10.3934/proc.2001.2001.295

2021 Impact Factor: 1.497