×

Langages algébriques de mots biinfinis. (Algebraic languages of biinfinite words). (French) Zbl 0742.68039

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.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
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.