Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-23T08:49:07.490Z Has data issue: false hasContentIssue false
  • English
  • Français

Codes générateurs minimaux de langages de mots bi-infinis

Published online by Cambridge University Press:  15 April 2002

Jeanne Devolder
Jeanne Devolder*
Affiliation:
Laboratoire de Statistique et Probabilités, F.R.E. CNRS 2222, Université des Sciences et Technologies de Lille, bâtiment M2, 59655 Villeneuve-d'Ascq, France ; ([email protected])
Get access

Abstract

In this paper we give two families of codes which are minimal generators of biinfinite languages: the family of very thin codes (which contains the rational codes) and another family containing the circular codes. We propose the conjecture that all codes are minimal generators.

Keywords

Mots bi-infinisbiω-générateurcodecode très mincecode rationnelcode circulairecode précirculairecode synchrone.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 34 , Issue 6 , November 2000 , pp. 585 - 596
Copyright
© EDP Sciences, 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Berstel et D. Perrin, Theory of codes. Academic Press, Orlando (1985).
D. Beauquier, Automates sur les mots bi-infinis. Thesis, University of Paris VII, France (1986).
V. Bruyère, Codes, Chapter 7, Algebraic Combinatorics on words, edited by M. Lothaire (to appear).
J. Devolder, Comportement des codes vis-à-vis des mots infinis et bi-infinis. Théorie des Automates et Applications, edited by D. Krob. Rouen, France (1991) 75-90.
Devolder, J. et Litovsky, I., Finitely generated bi $\omega$ -langages. Theoret. Comput. Sci. 85 (1991) 33-52. CrossRef
Devolder, J. et Timmerman, E., Finitary codes for biinfinite words. RAIRO: Theoret. Informatics Appl. 26 (1992) 363-386.
Devolder, J., Precircular codes and periodic bi-infinite words. Inform. and Comput. 107 (1993) 185-201. CrossRef
J. Devolder, Codes, mots infinis et bi-infinis. Ph.D. Thesis, University of Lille I, France (1993).
Devolder, J., Latteux, M., Litovsky, I. et Staiger, L., Codes and infinite words. Acta Cybernet. 11 (1994) 241-256.
Gire, F. et Nivat, M., Langages algébriques de mots bi-infinis. Theoret. Comput. Sci. 86 (1991) 277-323. CrossRef
Lassez, J.-L., Circular codes and synchronisation. Internat. J. Comput. Inform. Sci. 5 (1976) 201-208. CrossRef
Litovsky, I., Prefix-free languages as $\omega$ -generators. Inform. Process. Lett. 37 (1991) 61-65. CrossRef
M. Nivat et D. Perrin, Ensembles reconnaissables de mots bi-infinis, in Proc. 14e ACM Symp. on Theory of Computing, Vol. 005 (1982) 47-59.