January  2016, 36(1): 403-422. doi: 10.3934/dcds.2016.36.403

On the Markov-Dyck shifts of vertex type

1. 

Department of Mathematics, Joetsu University of Education, Joetsu 943-8512

Received  May 2014 Revised  April 2015 Published  June 2015

For a given finite directed graph $G$, there are two types of Markov-Dyck shifts, the Markov-Dyck shift $D_G^V$ of vertex type and the Markov-Dyck shift $D_G^E$ of edge type. It is shown that, if $G$ does not have multi-edges, the former is a finite-to-one factor of the latter, and they have the same topological entropy. An expression for the zeta function of a Markov-Dyck shift of vertex type is given. It is different from that of the Markov-Dyck shift of edge type.
Citation: Kengo Matsumoto. On the Markov-Dyck shifts of vertex type. Discrete & Continuous Dynamical Systems - A, 2016, 36 (1) : 403-422. doi: 10.3934/dcds.2016.36.403
References:
[1]

M.-P. Béal, M. Blockelet and C. Dima, Sofic-Dick shifts,, preprint, (). Google Scholar

[2]

A. Costa and B. Steinberg, A categorical invariant of flow equivalence of shifts,, Ergodic Theory and Dynamical Systems, 74 (2014). doi: 10.1017/etds.2014.74. Google Scholar

[3]

J. Cuntz, Simple $C^*$-algebras generated by isometries,, Commun. Math. Phys., 57 (1977), 173. doi: 10.1007/BF01625776. Google Scholar

[4]

J. Cuntz and W. Krieger, A class of $C^*$-algebras and topological Markov chains,, Inventions Math., 56 (1980), 251. doi: 10.1007/BF01390048. Google Scholar

[5]

E. Deutsch, Dyck path enumeration,, Discrete Math., 204 (1999), 167. doi: 10.1016/S0012-365X(98)00371-9. Google Scholar

[6]

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration,, John Wiley, (1983). Google Scholar

[7]

T. Hamachi, K. Inoue and W. Krieger, Subsystems of finite type and semigroup invariants of subshifts,, J. Reine Angew. Math., 632 (2009), 37. doi: 10.1515/CRELLE.2009.049. Google Scholar

[8]

T. Hamachi and W. Krieger, A construction of subshifts and a class of semigroups,, preprint, (). Google Scholar

[9]

F. Harry, Line graphs, in, Graph Theory, (1972), 71. Google Scholar

[10]

G. Keller, Circular codes, loop counting, and zeta-functions,, J. Combinatorial Theory, 56 (1991), 75. doi: 10.1016/0097-3165(91)90023-A. Google Scholar

[11]

B. P. Kitchens, Symbolic Dynamics,, Springer-Verlag, (1998). doi: 10.1007/978-3-642-58822-8. Google Scholar

[12]

W. Krieger, On the uniqueness of the equilibrium state,, Math. Systems Theory, 8 (1974), 97. doi: 10.1007/BF01762180. Google Scholar

[13]

W. Krieger, On a syntactically defined invariant of symbolic dynamics,, Ergodic Theory Dynam. Systems, 20 (2000), 501. doi: 10.1017/S0143385700000249. Google Scholar

[14]

W. Krieger, On subshifts and semigroups,, Bull. London Math., 38 (2006), 617. doi: 10.1112/S0024609306018625. Google Scholar

[15]

W. Krieger and K. Matsumoto, Zeta functions and topological entropy of the Markov Dyck shifts,, Münster J. Math., 4 (2011), 171. Google Scholar

[16]

W. Krieger and K. Matsumoto, Markov-Dyck shifts, neutral periodic points and topological conjugacy (tentative title),, in preparation., (). Google Scholar

[17]

D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding,, Cambridge University Press, (1995). doi: 10.1017/CBO9780511626302. Google Scholar

[18]

K. Matsumoto, Cuntz-Krieger algebras and a generalization of Catalan numbers,, Int. J. Math., 24 (2013). doi: 10.1142/S0129167X13500407. Google Scholar

[19]

K. Matsumoto, $C^*$-algebras arising from Dyck systems of topological Markov chains,, Math. Scand., 109 (2011), 31. Google Scholar

[20]

R. P. Stanley, Enumerative Combinatrics I,, Wadsworth & Brooks/Cole Advanced Books, (1986). doi: 10.1007/978-1-4615-9763-6. Google Scholar

show all references

References:
[1]

M.-P. Béal, M. Blockelet and C. Dima, Sofic-Dick shifts,, preprint, (). Google Scholar

[2]

A. Costa and B. Steinberg, A categorical invariant of flow equivalence of shifts,, Ergodic Theory and Dynamical Systems, 74 (2014). doi: 10.1017/etds.2014.74. Google Scholar

[3]

J. Cuntz, Simple $C^*$-algebras generated by isometries,, Commun. Math. Phys., 57 (1977), 173. doi: 10.1007/BF01625776. Google Scholar

[4]

J. Cuntz and W. Krieger, A class of $C^*$-algebras and topological Markov chains,, Inventions Math., 56 (1980), 251. doi: 10.1007/BF01390048. Google Scholar

[5]

E. Deutsch, Dyck path enumeration,, Discrete Math., 204 (1999), 167. doi: 10.1016/S0012-365X(98)00371-9. Google Scholar

[6]

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration,, John Wiley, (1983). Google Scholar

[7]

T. Hamachi, K. Inoue and W. Krieger, Subsystems of finite type and semigroup invariants of subshifts,, J. Reine Angew. Math., 632 (2009), 37. doi: 10.1515/CRELLE.2009.049. Google Scholar

[8]

T. Hamachi and W. Krieger, A construction of subshifts and a class of semigroups,, preprint, (). Google Scholar

[9]

F. Harry, Line graphs, in, Graph Theory, (1972), 71. Google Scholar

[10]

G. Keller, Circular codes, loop counting, and zeta-functions,, J. Combinatorial Theory, 56 (1991), 75. doi: 10.1016/0097-3165(91)90023-A. Google Scholar

[11]

B. P. Kitchens, Symbolic Dynamics,, Springer-Verlag, (1998). doi: 10.1007/978-3-642-58822-8. Google Scholar

[12]

W. Krieger, On the uniqueness of the equilibrium state,, Math. Systems Theory, 8 (1974), 97. doi: 10.1007/BF01762180. Google Scholar

[13]

W. Krieger, On a syntactically defined invariant of symbolic dynamics,, Ergodic Theory Dynam. Systems, 20 (2000), 501. doi: 10.1017/S0143385700000249. Google Scholar

[14]

W. Krieger, On subshifts and semigroups,, Bull. London Math., 38 (2006), 617. doi: 10.1112/S0024609306018625. Google Scholar

[15]

W. Krieger and K. Matsumoto, Zeta functions and topological entropy of the Markov Dyck shifts,, Münster J. Math., 4 (2011), 171. Google Scholar

[16]

W. Krieger and K. Matsumoto, Markov-Dyck shifts, neutral periodic points and topological conjugacy (tentative title),, in preparation., (). Google Scholar

[17]

D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding,, Cambridge University Press, (1995). doi: 10.1017/CBO9780511626302. Google Scholar

[18]

K. Matsumoto, Cuntz-Krieger algebras and a generalization of Catalan numbers,, Int. J. Math., 24 (2013). doi: 10.1142/S0129167X13500407. Google Scholar

[19]

K. Matsumoto, $C^*$-algebras arising from Dyck systems of topological Markov chains,, Math. Scand., 109 (2011), 31. Google Scholar

[20]

R. P. Stanley, Enumerative Combinatrics I,, Wadsworth & Brooks/Cole Advanced Books, (1986). doi: 10.1007/978-1-4615-9763-6. Google Scholar

[1]

Wolfgang Krieger, Kengo Matsumoto. Markov-Dyck shifts, neutral periodic points and topological conjugacy. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 1-18. doi: 10.3934/dcds.2019001

[2]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

[3]

Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete & Continuous Dynamical Systems - A, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191

[4]

Silvère Gangloff, Benjamin Hellouin de Menibus. Effect of quantified irreducibility on the computability of subshift entropy. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 1975-2000. doi: 10.3934/dcds.2019083

[5]

Michael Schraudner. Projectional entropy and the electrical wire shift. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 333-346. doi: 10.3934/dcds.2010.26.333

[6]

Manfred G. Madritsch. Non-normal numbers with respect to Markov partitions. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 663-676. doi: 10.3934/dcds.2014.34.663

[7]

João Ferreira Alves, Michal Málek. Zeta functions and topological entropy of periodic nonautonomous dynamical systems. Discrete & Continuous Dynamical Systems - A, 2013, 33 (2) : 465-482. doi: 10.3934/dcds.2013.33.465

[8]

A. Crannell. A chaotic, non-mixing subshift. Conference Publications, 1998, 1998 (Special) : 195-202. doi: 10.3934/proc.1998.1998.195

[9]

Fernando Luque-Vásquez, J. Adolfo Minjárez-Sosa. Average optimal strategies for zero-sum Markov games with poorly known payoff function on one side. Journal of Dynamics & Games, 2014, 1 (1) : 105-119. doi: 10.3934/jdg.2014.1.105

[10]

Roland Martin. On simple Igusa local zeta functions. Electronic Research Announcements, 1995, 1: 108-111.

[11]

Simon Scott. Relative zeta determinants and the geometry of the determinant line bundle. Electronic Research Announcements, 2001, 7: 8-16.

[12]

Van Cyr, John Franks, Bryna Kra, Samuel Petite. Distortion and the automorphism group of a shift. Journal of Modern Dynamics, 2018, 13: 147-161. doi: 10.3934/jmd.2018015

[13]

Peng Sun. Exponential decay of Lebesgue numbers. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3773-3785. doi: 10.3934/dcds.2012.32.3773

[14]

Danny Calegari, Alden Walker. Ziggurats and rotation numbers. Journal of Modern Dynamics, 2011, 5 (4) : 711-746. doi: 10.3934/jmd.2011.5.711

[15]

Xavier Buff, Nataliya Goncharuk. Complex rotation numbers. Journal of Modern Dynamics, 2015, 9: 169-190. doi: 10.3934/jmd.2015.9.169

[16]

Daniel Gonçalves, Marcelo Sobottka. Continuous shift commuting maps between ultragraph shift spaces. Discrete & Continuous Dynamical Systems - A, 2019, 39 (2) : 1033-1048. doi: 10.3934/dcds.2019043

[17]

Michael Baake, John A. G. Roberts, Reem Yassawi. Reversing and extended symmetries of shift spaces. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 835-866. doi: 10.3934/dcds.2018036

[18]

James Kingsbery, Alex Levin, Anatoly Preygel, Cesar E. Silva. Dynamics of the $p$-adic shift and applications. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 209-218. doi: 10.3934/dcds.2011.30.209

[19]

Michael Björklund, Alexander Gorodnik. Central limit theorems in the geometry of numbers. Electronic Research Announcements, 2017, 24: 110-122. doi: 10.3934/era.2017.24.012

[20]

David Karpuk, Anne-Maria Ernvall-Hytönen, Camilla Hollanti, Emanuele Viterbo. Probability estimates for fading and wiretap channels from ideal class zeta functions. Advances in Mathematics of Communications, 2015, 9 (4) : 391-413. doi: 10.3934/amc.2015.9.391

2018 Impact Factor: 1.143

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]