Finitary codes for biinfinite words. (English) Zbl 0754.68066

Summary: The aim of decoding, or factorizing a single way, biinfinite words with a finitary language leads to define, according to the definition of factorizations, two distinct notions of finitary codes for biinfinite words we call “\(bi\omega\)-codes” and “\(\mathbb{Z}\)-codes”. These codes are respectively close to the precircular codes and to the circular codes. The notion of \(bi\omega\)-code is weaker but seems to be more suitable for biinfinite words. Indeed, \(bi\omega\)-codes are characterized using coding morphisms, as are usual codes and codes for infinite words. \(\mathbb{Z}\)-codes are rather codes for \(\mathbb{Z}\)-words. The relationships between all these finitary codes are studied, and characteristic properties of \(bi\omega\)- codes and \(\mathbb{Z}\)-codes are given.


68Q45 Formal languages and automata
Full Text: DOI EuDML


[1] 1. E. BARBIN-LE REST and M. LE REST, Sur la combinatoire des codes à deux mots, Theor. Comp. Sc., 1985, 41, pp. 61-80. Zbl0593.20066 MR841023 · Zbl 0593.20066 · doi:10.1016/0304-3975(85)90060-X
[2] 2. M. P. BEAL, Codages, automates locaux et entropie, Thèse, Publications du L.I.T.P., 38, Université de Paris-VII, 1988.
[3] 3. D. BEAUQUIER, Automates sur les mots biinfinis, Thèse d’état, Université Paris-VII, 1986.
[4] 4. J. BERSTEL and D. PERRIN, Theory of Codes, Academic Press, Orlando, 1985. Zbl0587.68066 MR797069 · Zbl 0587.68066
[5] 5. F. BLANCHARD, Codes engendrant certains systèmes sofiques, Theoret. Comput. Sci., 1989, 68, pp. 253-265. Zbl0683.28009 MR1031960 · Zbl 0683.28009 · doi:10.1016/0304-3975(89)90163-1
[6] 6. J. DEVOLDER, Precircular Codes and Periodic Biinfinite Words, Publications du L.I.F.L., I.T. 175, 1989, Inform. and Comput. (to appear). Zbl0790.94007 MR1251618 · Zbl 0790.94007 · doi:10.1006/inco.1993.1066
[7] 7. J. DEVOLDER, M. LATTEUX, I. LITOVSKY and L. STAIGER, Codes and Infinite Words, Publications du L.I.F.L., I.T. 220, 1991.
[8] 8. J. DEVOLDER and E. TIMMERMAN, Codes for Biinfinite Words, Publications du L.I.F.L., I.T. 194, 1990. · Zbl 0754.68066
[9] 9. DO LONG VAN, Codes avec des mots infinis, R.A.I.R.O. Inform. Theor. Appl., 1982, 16, pp. 371-386. Zbl0498.68053 · Zbl 0498.68053
[10] 10. DO LONG VAN, D. G. THOMAS, K. G. SUBRAMANIAN and R. SIROMONEY, Bi-Infinitary Codes, RAIRO Inform. Theor. Appl. , 1990, 24, 1, pp. 67-87. Zbl0701.68061 · Zbl 0701.68061
[11] 11. S. EILENBERG, Automata, Languages, and Machines, Academic Press, New York, 1974.
[12] 12. J. KARHUMAKI, On Three-Element Codes, Theoret. Comput.Sci., 1985, 40, pp. 3-11. Zbl0574.68062 · Zbl 0574.68062 · doi:10.1016/0304-3975(85)90155-0
[13] 13. J. L. LASSEZ, Circular codes and synchronisation, Internat. J. Comput. Syst. Sci., 1976, 5, pp. 201-208. Zbl0401.68050 · Zbl 0401.68050 · doi:10.1007/BF00975632
[14] 14. M. LECONTE, K-th Power-Free Codes, Automata on infinite words, Lecture notes in Comput. Sci., 1984, 192, pp. 172-187. Zbl0571.68054 · Zbl 0571.68054
[15] 15. A. LENTIN and M. P. SCHUTZENBERGER, A Combinatorial Problem in the Theory of Free Monoids, Proc. Univ. of North Carolina, 1967, pp. 128-144. Zbl0221.20076 · Zbl 0221.20076
[16] 16. I. LITOVSKY, Générateurs des langages rationnels de mots infinis, Thèse, Université de Lille-I, 1988.
[17] 17. A. DE LUCA and A. RESTIVO, On Some Properties of Very Pure Codes, Theoret. Comput. Sci., 1980, pp. 157-170. Zbl0421.68078 MR551602 · Zbl 0421.68078 · doi:10.1016/0304-3975(80)90012-2
[18] 18. M. NIVAT and D. PERRIN, Ensembles reconnaissables de mots biinfinis, Proc. 14e Symp. on Theory of Computing, 1982, pp.47-59. · Zbl 0589.68056
[19] 19. A. RESTIVO, Codes and automata, Lecture notes in Comput. Sci., 1989, 386, pp. 186-198. MR1051960
[20] 20. L. STAIGER, On Infinitary Finite Length Codes, R.A.I.R.O., Inform. Théor. Appl., 1986, 20, 4, pp. 483-494. Zbl0628.68056 MR880849 · Zbl 0628.68056
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.