Bi-infinitary codes. (English) Zbl 0701.68061

Summary: The notion of bi-infinitary codes is introduced. For this purpose, the monoid \(^{\infty}A^{\infty}\) of finite, infinite and bi-infinite words over an alphabet A is defined. A necessary and sufficient condition for a set of words to be a bi-infinitary code is formulated. Conditions for a submonoid of \(^{\infty}A^{\infty}\) to have a minimal generator set are established. Using a specific kind of Thue system, the notion of bi-quasi free sub-monoids is introduced. An “algebraic” characterization of the submonoids generated by bi-infinitary codes is obtained. Finally, a “combinatorial” characterization of bi-quasi free submonoids is studied.


68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
94A45 Prefix, length-variable, comma-free codes
Full Text: DOI EuDML


[1] 1. J. BERSTEL and D. PERRIN, Theory of Codes, Academic Press, 1985. Zbl0587.68066 MR797069 · Zbl 0587.68066
[2] 2. R. V. BOOK, Thue Systems and Church-Rosser Property: Replacement Systems, Specification of Formal Languages and Presentations of Monoids, in Combinatorics on Words, L. CUMMING Ed., Academic Press, 1983, pp. 1-38. Zbl0563.68062 MR910127 · Zbl 0563.68062
[3] 3. DO LONGVAN, Codes avec des mots infinis, R.A.I.R.O. inform. Theor., Vol.16, 1982, pp. 371-386. Zbl0498.68053 MR707638 · Zbl 0498.68053
[4] 4. DO LONG VAN, Sous-monoïdes et codes avec des mots infinis, Semigroup Forum, Vol. 26, 1983, pp. 75-87. Zbl0504.68054 MR685117 · Zbl 0504.68054 · doi:10.1007/BF02572821
[5] 5. DO LONG VAN, Ensembles code - Compatibles et une généralisation du théorème de Sardinas/Patterson, Theor. Comp. Science, Vol. 38, 1985, pp. 123-132. Zbl0574.20053 MR805138 · Zbl 0574.20053 · doi:10.1016/0304-3975(85)90214-2
[6] 6. DO LONG VAN, Sur les ensembles générateurs minimaux des sous-monoïdes de A\infty , C. R. Acad. Sci. Paris, 300, Série I, 1985, pp. 443-446. Zbl0578.68063 MR794019 · Zbl 0578.68063
[7] 7. DO LONG VAN, Caractérisations combinatoires des sous-monoïdes engendrés par un code infinitaire, Hanoi Preprint Séries, No. 6, 1984.
[8] 8. DO LONG VAN, Languages écrits par un code infinitaire, Théorème du défaut, Acta Cybernetica, Vol. 7, 1986, pp. 247-257. Zbl0611.68046 MR829305 · Zbl 0611.68046
[9] 9. DO LONG VAN, Codes infinitaires et automates non-ambigus, C. R. Acad. Sci. Paris, T. 302, Séries I, 1986, pp. 693-696. Zbl0602.68069 MR847756 · Zbl 0602.68069
[10] 10. DO LONG VAN, Contribution to Combinatorics on Words, Publication of L.I.T.P., No. 29, 1985.
[11] 11. S. EILENBERG, Automata, Languages and Machines, Vol. A, Academic Press, New York/London, 1974. Zbl0317.94045 MR530382 · Zbl 0317.94045
[12] 12. G. LALLEMENT, Semigroups and Combinatorial Application, Wiley, New York, 1979. Zbl0421.20025 MR530552 · Zbl 0421.20025
[13] 13. M. NIVAT, Éléments de la théorie générale des codes, in Automata Theory, E. R. CAIANIELLO Ed.) Academic Press, New York/London, 1966, pp. 278-294. Zbl0208.45101 MR241168 · Zbl 0208.45101
[14] 14. M. NIVAT and A. ARNOLD, Comportements de processus, in Colloque, Les Mathématiques de l’Informatique, Paris, 1982, pp. 35-68. Zbl0538.68062 · Zbl 0538.68062
[15] 15. M. NIVAT and D. PERRIN, Ensembles reconnaissables de mots biinfinis, Canad. J. Math., Vol. XXXVIII, No. 3, 1986, pp. 513-537. Zbl0619.68067 MR845662 · Zbl 0619.68067 · doi:10.4153/CJM-1986-025-6
[16] 16. M. P. SCHÜTZENBERGER, Une théorie algébrique du codage, Séminaire Dubrail, expose No. 15, Algebre et théorie des nombres, année 1955-1956. MR75169
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.