On the structure of a sofic shift space

Thomsen, Klaus

doi:10.1090/S0002-9947-04-03437-3

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