An ω-Power of a Finitary Language Which is a Borel Set of Infinite Rank

• Autorzy: Finkel O.
• Języki publikacji: EN

Abstrakty

EN

ω-powers of finitary languages are ω-languages s in the form V^ω, where V is a finitary language over a finite alphabet Σ. Since the set Σ,sup>ω of infinite words over Σ can be equipped with the usual Cantor topology, the question of the topological complexity of ω-powers naturally arises and has been raised by Niwinski [13], by Simonnet [15], and by Staiger [18]. It has been proved in [4] that for each integer n ≥ 1, there exist some ω-powers of context free languages which are Π_n⁰-complete Borel sets, and in [5] that there exists a context free language L such that L^ω is analytic but not Borel. But the question was still open whether there exists a finitary language V such that V^ω is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose ω-power is Borel of infinite rank.

Słowa kluczowe

EN

infinite words; w-languages; w-powers; Cantor topology; topological complexity; Borel sets; infinite rank

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 62, nr 3,4
• Strony: 333--342
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Finkel O.

• Equipe de Logique Mathématique, U.F.R. de Mathématiques, Université Paris 7, 2 Place Jussieu, 75251 Paris, cedex 05, France,

Bibliografia

• [1] Autebert, J.-M., Berstel, J., Boasson, L.: Context free languages and pushdown automata, in: Handbook of formal languages, Vol. 1, Springer-Verlag, 1996.
• [2] Berstel, J.: Transductions and context free languages, Teubner Studienbcher Informatik, 1979.
• [3] Duparc, J.: Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank, Journal of Symbolic Logic, 66{l), 2001,56-S6.
• [4] Finkel, O.: Topological properties of omega context free languages. Theoretical Computer Science, 262(1-2), 2001,669-697.
• [5] Finkel, O.: Borel hierarchy and omega context free languages. Theoretical Computer Science, 290(3), 2003, 1385-1405.
• [6] Finkel, O., Simonnet, P.: Topology and ambiguity in omega context free languages. Bulletin of the Belgian Mathematical Society, 10(5), 2003, 707-722.
• [7] Hopcroft, J. E., Ullman, J. D.: Introduction to automata theory, languages, and computation, Addison-Wesley Publishing Co., Reading, Mass., 1979, Addison-Wesley Series in Computer Science.
• [8] Kechris, A. S.: Classical descriptive set theory. Springer-Verlag, New York, 1995, ISBN 0-387-94374-9.
• [9] Kuratowski, K.: Topology, Academic Press, New York, 1966.
• [10] Lecomte, D.: Sur les ensembles de phrases infinies constructibles a partir d'un dictionnaire sur un alphabet fini, in: Sminaire d'Initiation a VAnalyse, Vol. 1, Universit Paris 6, 2001-2002.
• [11] Lescow, H., Thomas, W.: Logical specifications of infinite computations, A Decade of Concurrency (J. W. de Bakker, W. P de Roever, G. Rozenberg, Eds.), 803, Springer, 1994.
• [12] Moschovakis, Y. N.: Descriptive set theory, North-Holland Publishing Co., Amsterdam, 1980, ISBN 0-444-85305-7.
• [13] Niwinski,D.: A problem on w-powers, 1990 Workshop on Logics and Recognizable Sets, University of Kiel, 1990.
• [14] Perrin, D., Pin, J.-E.: Infinite words, automata, semigroups, logic and games, vol. 141 of Pure and Applied Mathematics, Elsevier, 2004.
• [15] Simonnet, P.: Automates et theorie descriptive, Ph.D. Thesis, Universit Paris VII, 1992.
• [16] Staiger, L.: Hierarchies of recursive w-languages, Elektronische Informationsverarbeitung und Kybernetik, 22(5-6), 1986,219-241, ISSN 0013-5712.
• [17] Staiger, L.; ω-languages, in; Handbook of formal languages. Vol. 3, Springer, Berlin, 1997,339-387.
• [18] Staiger, L.; On ω-power languages, in: New Trends in Formal Languages, Control, Coperation, and Combinatorics, vol. 1218 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1997,377-393.
• [19] Thomas, W.; Automata on infinite objects, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Formal models and semantics, Elsevier, 1990, 135-191.