×

A hierarchy of shift equivalent sofic shifts. (English) Zbl 1079.68048

Summary: We define new subclasses of the class of irreducible sofic shifts. These classes form an infinite hierarchy where the lowest class is the class of almost finite type shifts introduced by B. Marcus. We give effective characterizations of these classes with the syntactic semigroups of the shifts. We prove that these classes define invariants for shift equivalence (and thus for conjugacy). Finally, we extend the result to the case of reducible sofic shifts.

MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] Béal, M.-P., Codage symbolique, (1993), Masson
[2] M.-P. Béal, F. Fiorenzi, D. Perrin, A hierarchy of irreducible sofic shifts, in: MFCS 2004, Lecture Notes in Computer Science, Vol. 3153, Springer, Berlin, 2004, pp. 611-622. · Zbl 1096.68078
[3] M.-P. Béal, F. Fiorenzi, D. Perrin, The syntactic graph of a sofic shift, in: STACS 2004, Lecture Notes in Computer Science, Vol. 2996, Springer, Berlin, 2004, pp. 282-293. · Zbl 1122.68463
[4] M.-P. Béal, F. Fiorenzi, D. Perrin, The syntactic graph of a sofic shift is invariant under shift equivalence, Internat. J. Algebra Comput. (2005), to appear. · Zbl 1098.68062
[5] Beauquier, D., Minimal automaton for a factorial transitive rational language, Theoret. comput. sci., 67, 65-73, (1989) · Zbl 0679.68110
[6] Berstel, J.; Perrin, D., Theory of codes, (1985), Academic Press New York · Zbl 1022.94506
[7] Blanchard, F., Codes engendrant certains systèmes sofiques, Theoret. comput. sci., 68, 253-265, (1989) · Zbl 0683.28009
[8] Boyle, M.; Kitchens, B.P.; Marcus, B.H., A note on minimal covers for sofic shifts, Proc. amer. math. soc., 95, 403-411, (1985) · Zbl 0606.28016
[9] M. Boyle, W. Krieger, Almost Markov and shift equivalent sofic systems, in: Dynamical Systems, Lecture Notes in Mathematics, Vol. 1342, Springer, 1988, pp. 33-93. · Zbl 0664.28007
[10] Fiebig, D.; Fiebig, U.-R.; Jonoska, N., Multiplicities of covers for sofic shifts, Theoret. comput. sci., 1-2, 349-375, (2001) · Zbl 0983.68143
[11] Hedlund, G.A., Endomorphisms and automorphisms of the shift dynamical system, Math. systems theory, 3, 320-337, (1969) · Zbl 0182.56901
[12] Jonoska, N., A conjugacy invariant for reducible sofic shifts and its semigroup characterizations, Israel J. math., 106, 221-249, (1998) · Zbl 0908.68111
[13] Karabed, R.; Marcus, B.H., Sliding-block coding for input-restricted channels, IEEE trans. inform. theory, 34, 2-26, (1988)
[14] Kim, K.H.; Roush, F.W., An algorithm for sofic shift equivalence, Ergodic theory dynam. systems, 10, 381-393, (1990) · Zbl 0674.20041
[15] Kim, K.H.; Roush, F.W., Williams’s conjecture is false for reducible subshifts, J. amer. math. soc., 5, 213-215, (1992) · Zbl 0749.54013
[16] Kitchens, B.P., Symbolic dynamics: one-sided, two-sided and countable state Markov shifts, (1997), Springer Berlin
[17] Krieger, W., On sofic systems. I, Israel J. math., 48, 305-330, (1984) · Zbl 0573.54032
[18] Lind, D.A.; Marcus, B.H., An introduction to symbolic dynamics and coding, (1995), Cambridge University Press Cambridge · Zbl 1106.37301
[19] Marcus, B.H., Sofic systems and encoding data, IEEE trans. inform. theory, IT-31, 366-377, (1985) · Zbl 0568.94015
[20] Margolis, S.W., On the syntactic transformation semigroup of a language generated by a finite biprefix code, Theoret. comput. sci., 21, 225-230, (1982) · Zbl 0486.68078
[21] Nasu, M., An invariant for bounded-to-one factor maps between transitive sofic subshifts, Ergodic theory dynam. systems, 5, 89-105, (1985) · Zbl 0603.54042
[22] Nasu, M., Topological conjugacy for sofic systems, Ergodic theory dynam. systems, 6, 265-280, (1986) · Zbl 0607.54026
[23] Pin, J.-É., Varieties of formal languages, (1986), Plenum Publishing Corporation New York · Zbl 0632.68069
[24] Thomsen, K., On the structure of a sofic shift space, Trans. amer. math. soc., 356, 3557-3619, (2004), (electronic) · Zbl 1260.37010
[25] Weiss, B., Subshifts of finite type and sofic systems, Monats. für math., 77, 462-474, (1973) · Zbl 0285.28021
[26] Williams, S., Covers of non-almost-finite-type systems, Proc. amer. math. soc., 104, 245-252, (1988) · Zbl 0664.28010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.