# American Institute of Mathematical Sciences

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. [2] J. Milnor and W. Thurston, On iterated maps of the interval,, in, (1342), 1986. [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. [4] J. P. Lampreia and S. Ramos, Kneading theory for tree maps,, Ergodic Theory and Dynamical Systems, 24 (2004), 957. 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. doi: 10.1080/1023619021000047752. [6] L. Sella and P. Collins, "Discrete Dynamics of Two-Dimensional Nonlinear Hybrid Automata,", Hybrid Systems: Computation and Control, (2008). [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. [8] T. Kaczynski, K. Mischaikow and M. Mrozek, "Computational Homology,", Applied Mathematical Sciences, (). [9] S. Day, O. Junge and M. Konstantin, Towards automated chaos verification,, EQUADIFF, (2003), 157. [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. [11] A. Szymczak, The Conley index for decompositions of isolated invariant sets,, Fundamenta Mathematicae, 148 (1995), 71. [12] P. Collins, Dynamics of surface diffeomorphisms relative to homoclinic and heteroclinic orbits,, Dynamical Systems, 19 (2004), 1. doi: 10.1080/14689360310001623421. [13] M. Misiurewicz, Strange attractors for the Lozi mappings,, Nonlinear Dynamics (Internat. Conf., (1979), 348. [14] A. Hatcher, "Algebraic Topology,", Cambridge University Press, (2002). [15] J. Munkres, "Elements of Algebraic Topology,", Addison-Wesley Publishing Company, (2002). [16] R. Gilmore and M. Lefranc, "The Topology of Chaos," Alice in Stretch and Squeezeland,, Wiley-Interscience [John Wiley & Sons], (1984). [17] D. Sand, Numerical computations on Lozi maps,, \url{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, (1995). doi: 10.1017/CBO9780511626302. [2] J. Milnor and W. Thurston, On iterated maps of the interval,, in, (1342), 1986. [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. [4] J. P. Lampreia and S. Ramos, Kneading theory for tree maps,, Ergodic Theory and Dynamical Systems, 24 (2004), 957. 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. doi: 10.1080/1023619021000047752. [6] L. Sella and P. Collins, "Discrete Dynamics of Two-Dimensional Nonlinear Hybrid Automata,", Hybrid Systems: Computation and Control, (2008). [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. [8] T. Kaczynski, K. Mischaikow and M. Mrozek, "Computational Homology,", Applied Mathematical Sciences, (). [9] S. Day, O. Junge and M. Konstantin, Towards automated chaos verification,, EQUADIFF, (2003), 157. [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. [11] A. Szymczak, The Conley index for decompositions of isolated invariant sets,, Fundamenta Mathematicae, 148 (1995), 71. [12] P. Collins, Dynamics of surface diffeomorphisms relative to homoclinic and heteroclinic orbits,, Dynamical Systems, 19 (2004), 1. doi: 10.1080/14689360310001623421. [13] M. Misiurewicz, Strange attractors for the Lozi mappings,, Nonlinear Dynamics (Internat. Conf., (1979), 348. [14] A. Hatcher, "Algebraic Topology,", Cambridge University Press, (2002). [15] J. Munkres, "Elements of Algebraic Topology,", Addison-Wesley Publishing Company, (2002). [16] R. Gilmore and M. Lefranc, "The Topology of Chaos," Alice in Stretch and Squeezeland,, Wiley-Interscience [John Wiley & Sons], (1984). [17] D. Sand, Numerical computations on Lozi maps,, \url{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 & 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] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] 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 [20] Lars Lamberg, Lauri Ylinen. Two-Dimensional tomography with unknown view angles. Inverse Problems & Imaging, 2007, 1 (4) : 623-642. doi: 10.3934/ipi.2007.1.623

2017 Impact Factor: 0.972