Gire, F.; Nivat, M. Langages algébriques de mots biinfinis. (Algebraic languages of biinfinite words). (French) Zbl 0742.68039 Theor. Comput. Sci. 86, No. 2, 277-323 (1991). A rational language of bi-infinite strings is a finite union of languages of the form \(^ \omega ABC^ \omega\), where \(A\), \(B\), \(C\) are usual regular languages. The aim of the paper is to define algebraic languages of bi-infinite strings. Three different approaches are used, leading to three different families, \({\mathcal C}_ 0\), \({\mathcal C}_ 1\), \({\mathcal C}_ 2\) for which the strict inclusions \({\mathcal C}_ 2\subset{\mathcal C}_ 1\subset{\mathcal C}_ 0\) hold. \({\mathcal C}_ 0\) is the infinite rational closure of algebraic (context-free, in the usual terminology) languages of finite strings, \({\mathcal C}_ 1\) is the family of languages of the form \(L^ \omega(G,v)\), of infinite strings generated by a context-free grammar \(G\) with the axiom \(v\), and \({\mathcal C}_ 2\) is the family of languages of infinite strings which are the adherence of context-free languages of finite strings. Reviewer: G.Paun (Bucureşti) Cited in 4 Documents MSC: 68Q45 Formal languages and automata Keywords:rational language of bi-infinite strings PDFBibTeX XMLCite \textit{F. Gire} and \textit{M. Nivat}, Theor. Comput. Sci. 86, No. 2, 277--323 (1991; Zbl 0742.68039) Full Text: DOI References: [1] Autebert, J.-M.; Beauquier, J.; Boasson, L.; Gire, F., Bicentres de langages algébriques, Acta Inform., 21, 209-227 (1984) · Zbl 0521.68087 [2] Beauquier, D., Bilimites de langages reconnaissables, Theoret. Comput. Sci., 33, 335-342 (1984) · Zbl 0555.68044 [3] Beauquier, D., Ensembles reconnaissables de mots biinfinis, Rapport L.I.T.P. no. 84-57 (1984) [4] Boasson, L.; Nivat, M., Adhérences of languages, J. Comput. System Sci., 20, 285-309 (1980) · Zbl 0471.68052 [5] De Luca, A.; Restivo, A.; Salemi, S., On the centers of a language, Theoret. Comput. Sci., 24, 21-34 (1983) · Zbl 0518.68043 [6] Gire, F., Relations rationnelles infinitaires, Thèse de troisième cycle, 7 (1981), Paris · Zbl 0552.68064 [7] Gire, F.; Nivat, M., Relations rationnelles infinitaires, Calcolo, XXI (1984), fasc. II · Zbl 0552.68064 [8] Nivat, M., Mots infinis engendrés par une grammaire algébrique, RAIRO Inform. Théor., 11, 311-327 (1977) · Zbl 0371.68025 [9] Nivat, M., Sur les ensembles de mots engendrés par une grammaire algébrique, RAIRO Inform. Théor., 12, 259-278 (1978) · Zbl 0387.68050 [10] M. Nivat et D. Perrin, Ensembles reconnaissables de mots biinfinis, in: Proc. 14th ACM Symp. on Theory of Computing, 47-59.; M. Nivat et D. Perrin, Ensembles reconnaissables de mots biinfinis, in: Proc. 14th ACM Symp. on Theory of Computing, 47-59. · Zbl 0619.68067 [11] Rosenberg, A. L., A machine realization of the linear context free languages, Inform. and Control, 10, 175-188 (1967) · Zbl 0149.24804 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.