# 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 & 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, (1995).  doi: 10.1017/CBO9780511626302.  Google Scholar [2] J. Milnor and W. Thurston, On iterated maps of the interval,, in, (1342), 1986.   Google Scholar [3] J. P. Lampreia and S. Ramos, Trimodal maps,, International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 3 (1993), 1607.  doi: 10.1142/S0218127493001276.  Google Scholar [4] J. P. Lampreia and S. Ramos, Kneading theory for tree maps,, Ergodic Theory and Dynamical Systems, 24 (2004), 957.  doi: 10.1017/S014338570400015X.  Google Scholar [5] J. L. Rocha and S. Ramos, On iterated maps of the interval with holes,, Journal of Difference Equations and Applications, 9 (2003), 319.  doi: 10.1080/1023619021000047752.  Google Scholar [6] L. Sella and P. Collins, "Discrete Dynamics of Two-Dimensional Nonlinear Hybrid Automata,", Hybrid Systems: Computation and Control, (2008).   Google Scholar [7] P. Collins, Symbolic dynamics from homoclinic tangles,, HInternational Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 12 (2002), 605.  doi: 10.1142/S0218127402004565.  Google Scholar [8] T. Kaczynski, K. Mischaikow and M. Mrozek, "Computational Homology,", Applied Mathematical Sciences, ().   Google Scholar [9] S. Day, O. Junge and M. Konstantin, Towards automated chaos verification,, EQUADIFF, (2003), 157.   Google Scholar [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.  doi: 10.1088/0951-7715/14/5/301.  Google Scholar [11] A. Szymczak, The Conley index for decompositions of isolated invariant sets,, Fundamenta Mathematicae, 148 (1995), 71.   Google Scholar [12] P. Collins, Dynamics of surface diffeomorphisms relative to homoclinic and heteroclinic orbits,, Dynamical Systems, 19 (2004), 1.  doi: 10.1080/14689360310001623421.  Google Scholar [13] M. Misiurewicz, Strange attractors for the Lozi mappings,, Nonlinear Dynamics (Internat. Conf., (1979), 348.   Google Scholar [14] A. Hatcher, "Algebraic Topology,", Cambridge University Press, (2002).   Google Scholar [15] J. Munkres, "Elements of Algebraic Topology,", Addison-Wesley Publishing Company, (2002).   Google Scholar [16] R. Gilmore and M. Lefranc, "The Topology of Chaos," Alice in Stretch and Squeezeland,, Wiley-Interscience [John Wiley & Sons], (1984).   Google Scholar [17] D. Sand, Numerical computations on Lozi maps,, \url{http://topo.math.u-psud.fr/ sands/Programs/Lozi/index.html}., ().   Google Scholar

show all references

##### References:
 [1] D. Lind and B. Marcus, "An Introduction To Symbolic Dynamics And Coding,", Cambridge University Press, (1995).  doi: 10.1017/CBO9780511626302.  Google Scholar [2] J. Milnor and W. Thurston, On iterated maps of the interval,, in, (1342), 1986.   Google Scholar [3] J. P. Lampreia and S. Ramos, Trimodal maps,, International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 3 (1993), 1607.  doi: 10.1142/S0218127493001276.  Google Scholar [4] J. P. Lampreia and S. Ramos, Kneading theory for tree maps,, Ergodic Theory and Dynamical Systems, 24 (2004), 957.  doi: 10.1017/S014338570400015X.  Google Scholar [5] J. L. Rocha and S. Ramos, On iterated maps of the interval with holes,, Journal of Difference Equations and Applications, 9 (2003), 319.  doi: 10.1080/1023619021000047752.  Google Scholar [6] L. Sella and P. Collins, "Discrete Dynamics of Two-Dimensional Nonlinear Hybrid Automata,", Hybrid Systems: Computation and Control, (2008).   Google Scholar [7] P. Collins, Symbolic dynamics from homoclinic tangles,, HInternational Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 12 (2002), 605.  doi: 10.1142/S0218127402004565.  Google Scholar [8] T. Kaczynski, K. Mischaikow and M. Mrozek, "Computational Homology,", Applied Mathematical Sciences, ().   Google Scholar [9] S. Day, O. Junge and M. Konstantin, Towards automated chaos verification,, EQUADIFF, (2003), 157.   Google Scholar [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.  doi: 10.1088/0951-7715/14/5/301.  Google Scholar [11] A. Szymczak, The Conley index for decompositions of isolated invariant sets,, Fundamenta Mathematicae, 148 (1995), 71.   Google Scholar [12] P. Collins, Dynamics of surface diffeomorphisms relative to homoclinic and heteroclinic orbits,, Dynamical Systems, 19 (2004), 1.  doi: 10.1080/14689360310001623421.  Google Scholar [13] M. Misiurewicz, Strange attractors for the Lozi mappings,, Nonlinear Dynamics (Internat. Conf., (1979), 348.   Google Scholar [14] A. Hatcher, "Algebraic Topology,", Cambridge University Press, (2002).   Google Scholar [15] J. Munkres, "Elements of Algebraic Topology,", Addison-Wesley Publishing Company, (2002).   Google Scholar [16] R. Gilmore and M. Lefranc, "The Topology of Chaos," Alice in Stretch and Squeezeland,, Wiley-Interscience [John Wiley & Sons], (1984).   Google Scholar [17] D. Sand, Numerical computations on Lozi maps,, \url{http://topo.math.u-psud.fr/ sands/Programs/Lozi/index.html}., ().   Google Scholar
 [1] Anke D. Pohl. Symbolic dynamics for the geodesic flow on two-dimensional hyperbolic good orbifolds. Discrete & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 2020, 40 (7) : 4379-4425. doi: 10.3934/dcds.2020184 [5] Simone Creo, Maria Rosaria Lancia, Alexander Nazarov, Paola Vernole. On two-dimensional nonlocal Venttsel' problems in piecewise smooth domains. Discrete & Continuous Dynamical Systems - S, 2019, 12 (1) : 57-64. doi: 10.3934/dcdss.2019004 [6] 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 [7] 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 [8] Ketty A. De Rezende, Mariana G. Villapouca. Discrete conley index theory for zero dimensional basic sets. Discrete & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 2006, 16 (2) : 393-394. doi: 10.3934/dcds.2006.16.393 [11] Micah Webster, Patrick Guidotti. Boundary dynamics of a two-dimensional diffusive free boundary problem. Discrete & Continuous Dynamical Systems - A, 2010, 26 (2) : 713-736. doi: 10.3934/dcds.2010.26.713 [12] Antonio Pumariño, José Ángel Rodríguez, Enrique Vigil. Renormalization of two-dimensional piecewise linear maps: Abundance of 2-D strange attractors. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 941-966. doi: 10.3934/dcds.2018040 [13] Luigi Ambrosio, Federico Glaudo, Dario Trevisan. On the optimal map in the $2$-dimensional random matching problem. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7291-7308. doi: 10.3934/dcds.2019304 [14] Hun Ki Baek, Younghae Do. Dangerous Border-Collision bifurcations of a piecewise-smooth map. Communications on Pure & Applied Analysis, 2006, 5 (3) : 493-503. doi: 10.3934/cpaa.2006.5.493 [15] Zhiying Qin, Jichen Yang, Soumitro Banerjee, Guirong Jiang. Border-collision bifurcations in a generalized piecewise linear-power map. Discrete & Continuous Dynamical Systems - B, 2011, 16 (2) : 547-567. doi: 10.3934/dcdsb.2011.16.547 [16] Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487 [17] Ming Zhao, Cuiping Li, Jinliang Wang, Zhaosheng Feng. Bifurcation analysis of the three-dimensional Hénon map. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 625-645. doi: 10.3934/dcdss.2017031 [18] Dyi-Shing Ou, Kenneth James Palmer. A constructive proof of the existence of a semi-conjugacy for a one dimensional map. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 977-992. doi: 10.3934/dcdsb.2012.17.977 [19] Todd Young. A result in global bifurcation theory using the Conley index. Discrete & Continuous Dynamical Systems - A, 1996, 2 (3) : 387-396. doi: 10.3934/dcds.1996.2.387 [20] M. C. Carbinatto, K. Mischaikow. Horseshoes and the Conley index spectrum - II: the theorem is sharp. Discrete & Continuous Dynamical Systems - A, 1999, 5 (3) : 599-616. doi: 10.3934/dcds.1999.5.599

2019 Impact Factor: 1.27