Some complete \(\omega \)-powers of a one-counter language, for any Borel class of finite rank

1. Autebert, J.-M., Berstel, J., Boasson, L.: Context free languages and pushdown automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1. Springer (1996)

2. Cohen, R.S., Gold, A.Y.: Theory of \(\omega \)-languages, parts one and two. J. Comput. Syst. Sci. 15, 169–208 (1977)

   Article  Google Scholar 

3. Duparc, J., Finkel, O.: An \(\omega \)-power of a context free language which is Borel above \({\Delta }_\omega ^0\). In: Proceedings of the International Conference Foundations of the Formal Sciences V: Infinite Games, November 26th to 29th, 2004, Bonn, Germany, volume 11 of College Publications at King’s College (Studies in Logic), pp. 109–122. London (2007)

4. Duparc, J.: Wadge hierarchy and Veblen hierarchy: part 1: Borel sets of finite rank. J. Symb. Log. 66(1), 56–86 (2001)

   Article  Google Scholar 

5. Finkel, O.: Topological properties of omega context free languages. Theor. Comput. Sci. 262(1–2), 669–697 (2001)

   Article  MathSciNet  Google Scholar 

6. Finkel, O.: Borel hierarchy and omega context free languages. Theor. Comput. Sci. 290(3), 1385–1405 (2003)

   Article  MathSciNet  Google Scholar 

7. Finkel, O.: An omega-power of a finitary language which is a Borel set of infinite rank. Fundam. Inf. 62(3–4), 333–342 (2004)

   MATH  Google Scholar 

8. Finkel, O.: Borel ranks and Wadge degrees of omega context free languages. Math. Struct. Comput. Sci. 16(5), 813–840 (2006)

   Article  Google Scholar 

9. Finkel, O., Lecomte, D.: There exist some \(\omega \)-powers of any Borel rank. In: Proceedings of the 16th EACSL Annual International Conference on Computer Science and Logic, CSL 2007, Lausanne, Switzerland, September 11–15, 2007, volume 4646 of Lecture Notes in Computer Science, pp. 115–129. Springer (2007)

10. Finkel, O., Lecomte, D.: Classical and effective descriptive complexities of omega-powers. Ann. Pure Appl. Log. 160(2), 163–191 (2009). arXiv:0708.4176

    Article  Google Scholar 

11. Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Co., Reading (2001). (Addison-Wesley Series in Computer Science)

    MATH  Google Scholar 

12. Kechris, A.S.: Classical Descriptive Set Theory. Springer, New York (1995)

    Book  Google Scholar 

13. Lecomte, D.: Omega-powers and descriptive set theory. J. Symb. Log. 70(4), 1210–1232 (2005)

    Article  Google Scholar 

14. Moschovakis, Y.N.: Descriptive Set Theory. North-Holland Publishing Co., Amsterdam (1980)

    MATH  Google Scholar 

15. Niwinski, D.: A problem on \(\omega \)-powers. In: 1990 Workshop on Logics and Recognizable Sets. University of Kiel (1990)

16. Perrin, D., Pin, J.-E.: Infinite Words, Automata, Semigroups, Logic and Games, volume 141 of Pure and Applied Mathematics. Elsevier, Amsterdam (2004)

    Google Scholar 

17. Simonnet, P.: Automates et théorie descriptive. Ph.D. thesis, Université Paris VII (1992)

18. Staiger, L.: Hierarchies of recursive \(\omega \)-languages. Elektronische Informationsverarbeitung und Kybernetik 22(5–6), 219–241 (1986)

    MathSciNet  MATH  Google Scholar 

19. Staiger, L.: \(\omega \)-languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 339–387. Springer, Berlin (1997)

20. Thomas, W.: Automata on infinite objects. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, volume B, Formal Models and Semantics, pp. 135–191. Elsevier, Amsterdam (1990)

    Google Scholar 

21. Wadge, W.: Reducibility and determinateness in the Baire space. Ph.D. thesis, University of California, Berkeley (1983)

Download references