Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
ω-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 Πn0-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.
Wydawca
Czasopismo
Rocznik
Tom
Strony
333--342
Opis fizyczny
Bibliogr. 19 poz.
Twórcy
autor
- Equipe de Logique Mathématique, U.F.R. de Mathématiques, Université Paris 7, 2 Place Jussieu, 75251 Paris, cedex 05, France, finkel@logique.jussieu.fr
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0005-0083