American Institute of Mathematical Sciences

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

On the Markov-Dyck shifts of vertex type

Kengo Matsumoto 1,

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.
Keywords: Catalan numbers., zeta function, subshift, Markov-Dyck shift, entropy.
Mathematics Subject Classification: Primary: 37B10; Secondary: 46L05, 05A1.
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]

Christian Wolf. A shift map with a discontinuous entropy function. Discrete & Continuous Dynamical Systems - A, 2020, 40 (1) : 319-329. doi: 10.3934/dcds.2020012
[3]

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
[4]

Ji-Cai Liu. Proof of Sun's conjectural supercongruence involving Catalan numbers. Electronic Research Archive, 2020, 28 (2) : 1023-1030. doi: 10.3934/era.2020054
[5]

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
[6]

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
[7]

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
[8]

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
[9]

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
[10]

James P. Kelly, Kevin McGoff. Entropy conjugacy for Markov multi-maps of the interval. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020353
[11]

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

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
[13]

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

[14]

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
[15]

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

[16]

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

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

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

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
[20]

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

2019 Impact Factor: 1.338

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences