On the structure of a sofic shift space
HTML articles powered by AMS MathViewer
- by Klaus Thomsen PDF
- Trans. Amer. Math. Soc. 356 (2004), 3557-3619 Request permission
Abstract:
The structure of a sofic shift space is investigated, and Krieger’s embedding theorem and Boyle’s factor theorem are generalized to a large class of sofic shifts.References
- Mike Boyle, Lower entropy factors of sofic systems, Ergodic Theory Dynam. Systems 3 (1983), no. 4, 541–557. MR 753922, DOI 10.1017/S0143385700002133
- Mike Boyle and Wolfgang Krieger, Almost Markov and shift equivalent sofic systems, Dynamical systems (College Park, MD, 1986–87) Lecture Notes in Math., vol. 1342, Springer, Berlin, 1988, pp. 33–93. MR 970547, DOI 10.1007/BFb0082823
- Mike Boyle, Bruce Kitchens, and Brian Marcus, A note on minimal covers for sofic systems, Proc. Amer. Math. Soc. 95 (1985), no. 3, 403–411. MR 806078, DOI 10.1090/S0002-9939-1985-0806078-7
- F. Blanchard and G. Hansel, Systèmes codés, Theoret. Comput. Sci. 44 (1986), no. 1, 17–49 (French, with English summary). MR 858689, DOI 10.1016/0304-3975(86)90108-8
- Ethan M. Coven and Michael E. Paul, Finite procedures for sofic systems, Monatsh. Math. 83 (1977), no. 4, 265–278. MR 461469, DOI 10.1007/BF01387905
- Peter Walters (ed.), Symbolic dynamics and its applications, Contemporary Mathematics, vol. 135, American Mathematical Society, Providence, RI, 1992. MR 1185076, DOI 10.1090/conm/135
- Doris Fiebig, Ulf-Rainer Fiebig, and Nataša Jonoska, Multiplicities of covers for sofic shifts, Theoret. Comput. Sci. 262 (2001), no. 1-2, 349–375. MR 1836227, DOI 10.1016/S0304-3975(00)00278-4
- B.M. Gurevič, Topological entropy of enumerable Markov chains, Soviet Math. Dokl. 10 (1969), 911-915.
- Nataša Jonoska, Sofic shifts with synchronizing presentations, Theoret. Comput. Sci. 158 (1996), no. 1-2, 81–115. MR 1388965, DOI 10.1016/0304-3975(96)00058-8
- Nataša Jonoska, A conjugacy invariant for reducible sofic shifts and its semigroup characterizations, Israel J. Math. 106 (1998), 221–249. MR 1656877, DOI 10.1007/BF02773470
- Wolfgang Krieger, On the subsystems of topological Markov chains, Ergodic Theory Dynam. Systems 2 (1982), no. 2, 195–202 (1983). MR 693975, DOI 10.1017/S0143385700001516
- Wolfgang Krieger, On sofic systems. I, Israel J. Math. 48 (1984), no. 4, 305–330. MR 776312, DOI 10.1007/BF02760631
- Wolfgang Krieger, On sofic systems. II, Israel J. Math. 60 (1987), no. 2, 167–176. MR 931874, DOI 10.1007/BF02790789
- Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092, DOI 10.1017/CBO9780511626302
- Brian Marcus, Sofic systems and encoding data, IEEE Trans. Inform. Theory 31 (1985), no. 3, 366–377. MR 794434, DOI 10.1109/TIT.1985.1057037
- Peter Walters (ed.), Symbolic dynamics and its applications, Contemporary Mathematics, vol. 135, American Mathematical Society, Providence, RI, 1992. MR 1185076, DOI 10.1090/conm/135
- Masakazu Nasu, An invariant for bounded-to-one factor maps between transitive sofic subshifts, Ergodic Theory Dynam. Systems 5 (1985), no. 1, 89–105. MR 782790, DOI 10.1017/S0143385700002777
- Masakazu Nasu, Topological conjugacy for sofic systems and extensions of automorphisms of finite subsystems of topological Markov shifts, Dynamical systems (College Park, MD, 1986–87) Lecture Notes in Math., vol. 1342, Springer, Berlin, 1988, pp. 564–607. MR 970572, DOI 10.1007/BFb0082848
- Karl Petersen, Chains, entropy, coding, Ergodic Theory Dynam. Systems 6 (1986), no. 3, 415–448. MR 863204, DOI 10.1017/S014338570000359X
- Paul Trow, Determining presentations of sofic shifts, Theoret. Comput. Sci. 259 (2001), no. 1-2, 199–216. MR 1832791, DOI 10.1016/S0304-3975(99)00336-9
Additional Information
- Klaus Thomsen
- Affiliation: Institut for matematiske fag, Ny Munkegade, 8000 Aarhus C, Denmark
- Email: matkt@imf.au.dk
- Received by editor(s): November 24, 2002
- Received by editor(s) in revised form: April 18, 2003
- Published electronically: January 16, 2004
- © Copyright 2004 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 356 (2004), 3557-3619
- MSC (2000): Primary 37B10
- DOI: https://doi.org/10.1090/S0002-9947-04-03437-3
- MathSciNet review: 2055747