Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-09T17:29:04.178Z Has data issue: false hasContentIssue false
  • English
  • Français

ω-powers and descriptive set theory

Published online by Cambridge University Press:  12 March 2014

Dominique Lecomte
Dominique Lecomte*
Affiliation:
Université Paris 6, Equipe D'Analyse Fonctionnelle, Tour 46-0. Boîte 186, 4. Place Jussieu 75 252 Paris Cedex 05., France Université de Picardie, I.U.T. de L'Oise Site de Creil, 13. Allée de La Faïencerie 60 107 Creil., France, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the sets of the infinite sentences constructible with a dictionary over a finite alphabet, from the viewpoint of descriptive set theory. Among others, this gives some true co-analytic sets. The case where the dictionary is finite is studied and gives a natural example of a set at level ω of the Wadge hierarchy.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 70 , Issue 4 , December 2005 , pp. 1210 - 1232
Copyright
Copyright © Association for Symbolic Logic 2005

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

REFERENCES

[1]Finkel, O., Topological properties of omega context free languages, Theoretical Computer Science, vol. 262 (2001), pp. 669–697.CrossRefGoogle Scholar
[2]Finkel, O., Borel hierarchy and omega context free languages, Theoretical Computer Science, vol. 290 (2003), no. 3, pp. 1385–1405.CrossRefGoogle Scholar
[3]Kechris, A. S., Classical descriptive set theory, Springer-Verlag, 1995.CrossRefGoogle Scholar
[4]Kechris, A. S., On the concept of Π11 -completeness, Proceedings of the American Mathematical Society, vol. 125 (1997), no. 6, pp. 1811–1814.CrossRefGoogle Scholar
[5]Levy, A., Basic set theory, Springer-Verlag, 1979.CrossRefGoogle Scholar
[6]Lothaire, M., Algebraic combinatorics on words, Cambridge University Press, 2002.CrossRefGoogle Scholar
[7]Louveau, A., A separation theorem for Σ11 sets, Transactions of the American Mathematical Society, vol. 260 (1980), pp. 363–378.Google Scholar
[8]Moschovakis, Y. N., Descriptive set theory, North-Holland, 1980.Google Scholar
[9]Simonnet, P., Automates et théorie descriptive, Ph.D. thesis, Université Paris 7, 03 1992.Google Scholar
[10]Staiger, L., ω-languages, Handbook of formal languages (Rozenberg, G. and Salomaa, A., editors), vol. 3. Springer-Verlag, 1997.Google Scholar
[11]Staiger, L., On ω-power languages, New trends in formal languages, control, cooperation and combinatorics, Lecture Notes in Computer Science, vol. 1218, Springer-Verlag, 1997. pp. 377–393.Google Scholar