Codes engendrant certains systèmes sofiques. (Codes generating certain sofic systems). (French) Zbl 0683.28009

The author defines the terms “local code” and “local code with finite splitting to the left and right” and shows that a sofic system is of finite type (respectively almost finite type) if and only if all first return codes are local (respectively local with unique splitting to the right and left).
A. Restivo [Inf. Control 25, 93-101 (1974; Zbl 0279.68054)] proved that finite circular codes generate subshifts of finite type. The author proves the following: (i) local codes are circular, (ii) finite local codes are identical to finite circular codes, (iii) finite codes with unique splitting are identical to finite codes with finite deciphering delay to the same side.
The paper finishes by showing that finite codes with unique splitting to the left and right generate almost finite type subshifts. This does not happen when the finiteness condition is dropped.
Reviewer: G.R.Goodson


28D05 Measure-preserving transformations
94B05 Linear codes (general theory)


Zbl 0279.68054
Full Text: DOI


[1] Béal, M.-P., Codages, automates locaux et entropie, (Thèse d’Etat (1988), Publications du LITP), 38
[2] Blanchard, F.; Hansel, G., Systèmes codés, Theoret. Comput. Sci., 44, 17-49 (1986) · Zbl 0601.68056
[3] Boyle, M.; Kitchens, B.; Marcus, B., A note on minimal covers for sofic systems, Proc. Amer. Math. Soc., 95, 3 (1985) · Zbl 0606.28016
[4] Berstel, J.; Perrin, D., Theory of Codes (1974), Academic Press: Academic Press London · Zbl 1022.94506
[5] Denker, M.; Grillenberger, C.; Sigmund, K., Ergodic Theory on Compact Spaces, (Lecture Notes in Mathematics, 527 (1976), Springer: Springer Berlin) · Zbl 0328.28008
[6] Eilenberg, S., (Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press London) · Zbl 0317.94045
[7] Krieger, W., On sofic systems I, Israel J. Math., 48, 305-330 (1984) · Zbl 0573.54032
[8] Marcus, B., Sofic systems and encoding data, IEEE Inform. Theory, 31, 179-186 (1985)
[9] Restivo, A., On a question of McNaughton and Papert, Inform. and Control, 25, 93-101 (1974) · Zbl 0279.68054
[10] A. Restivo, Codes and local constraints, Preprint.; A. Restivo, Codes and local constraints, Preprint. · Zbl 0693.68047
[11] Weiss, B., Subshifts of finite type and sofic systems, Monatsh. Math., 77, 462-474 (1973) · Zbl 0285.28021
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.