Document Open Access Logo

Polishness of Some Topologies Related to Automata

Authors Olivier Carton, Olivier Finkel, Dominique Lecomte

PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.22.pdf
  • Filesize: 457 kB
  • 16 pages

Document Identifiers

Author Details

Olivier Carton
Olivier Finkel
Dominique Lecomte

Cite As Get BibTex

Olivier Carton, Olivier Finkel, and Dominique Lecomte. Polishness of Some Topologies Related to Automata. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CSL.2017.22

Abstract

We prove that the Büchi topology, the automatic topology, the alphabetic topology and the strong alphabetic topology are Polish, and provide consequences of this.

Subject Classification

Keywords
  • Automata and formal languages; logic in computer science; infinite words; Büchi automaton; regular omega-language; Cantor space; finer topologies; Büc

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. R. Büchi. On a decision method in restricted second order arithmetic. In Stanford University Press, editor, Proceedings of the 1960 International Congress on Logic Methodology and Philosophy of Science, pages 1-11. Stanford University Press, 1962. Google Scholar
  2. C. Choffrut and S. Grigorieff. Uniformization of rational relations. In Juhani Karhumäki, Hermann A. Maurer, Gheorghe Paun, and Grzegorz Rozenberg, editors, Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pages 59-71. Springer, 1999. Google Scholar
  3. R. S. Cohen and A. Y. Gold. ω-computations on Turing machines. Theoretical Computer Science, 6:1-23, 1978. Google Scholar
  4. V. Diekert and M. Kufleitner. Fragments of first-order logic over infinite words. In S. Albers and J.-Y. Marion, eds., STACS 2009, Freiburg, Germany, February 26-28, 2009, Proceedings, pages 325-336, 2009. Online proceedings at DROPS and HAL, 2009. Google Scholar
  5. J. Duparc, O. Finkel, and J.-P. Ressayre. The Wadge hierarchy of Petri nets ω-languages. In V. Brattka, H. Diener, and D. Spreen, editors, Logic, Computation, Hierarchies, volume 4 of Ontos Mathematical Logic, collection of papers published in Honor of Victor Selivanov at the occasion of his sixtieth birthday, pages 109-138. Ontos-Verlag, 2014. Google Scholar
  6. O. Finkel. Borel ranks and Wadge degrees of omega context free languages. Mathematical Structures in Computer Science, 16(5):813-840, 2006. Google Scholar
  7. O. Finkel. The complexity of infinite computations in models of set theory. Logical Methods in Computer Science, 5(4:4):1-19, 2009. Google Scholar
  8. O. Finkel. Ambiguity of ω-languages of Turing machines. Logical Methods in Computer Science, 10(3:12):1-18, 2014. Google Scholar
  9. O. Finkel and D. Lecomte. Classical and effective descriptive complexities of ω-powers. Annals of Pure and Applied Logic, 160(2):163-191, 2009. Google Scholar
  10. O. Finkel and D. Lecomte. Decision problems for Turing machines. Information Processing Letters, 109:1223-1226, 2009. Google Scholar
  11. O. Finkel and P. Simonnet. Topology and ambiguity in omega context free languages. Bulletin of the Belgian Mathematical Society, 10(5):707-722, 2003. Google Scholar
  12. E. Grädel, W. Thomas, and W. Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002. Google Scholar
  13. L. A. Harrington, A. S. Kechris, and A. Louveau. A Glimm-Effros dichotomy for Borel equivalence relations. Journal of the American Mathematical Society, 3:903-928, 1990. Google Scholar
  14. S. Hoffmann, S. Schwarz, and L. Staiger. Shift-invariant topologies for the Cantor space X^ω. Theoretical Computer Science, 679:145–161, 2017. Google Scholar
  15. S. Hoffmann and L. Staiger. Subword metrics for infinite words. In Frank Drewes, editor, Implementation and Application of Automata - 20th International Conference, CIAA 2015, Umeå, Sweden, August 18-21, 2015, Proceedings, volume 9223 of Lecture Notes in Computer Science, pages 165-175. Springer, 2015. Google Scholar
  16. A. S. Kechris. Classical descriptive set theory. Springer-Verlag, New York, 1995. Google Scholar
  17. A. S. Kechris, S. Solecki, and S. Todorcevic. Borel chromatic numbers. Advances in Mathematics, 141(1):1-44, 1999. Google Scholar
  18. L. H. Landweber. Decision problems for ω-automata. Mathematical Systems Theory, 3(4):376-384, 1969. Google Scholar
  19. D. Lecomte. A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension. Transactions of the American Mathematical Society, 361(8):4181-4193, 2009. Google Scholar
  20. D. Lecomte. Potential Wadge classes. Memoirs of the American Mathematical Society, 221(1038):vi+83, 2013. Google Scholar
  21. H. Lescow and W. Thomas. Logical specifications of infinite computations. In J. W. de Bakker, Willem P. de Roever, and Grzegorz Rozenberg, editors, A Decade of Concurrency, volume 803 of Lecture Notes in Computer Science, pages 583-621. Springer, 1994. Google Scholar
  22. M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2002. Google Scholar
  23. A. Louveau. Ensembles analytiques et boréliens dans les espaces produit, volume 78. Astérisque (SMF), 1980. Google Scholar
  24. Y. N. Moschovakis. Descriptive set theory, volume 155 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, second edition, 2009. Google Scholar
  25. D. Perrin and J.-E. Pin. Infinite words, automata, semigroups, logic and games, volume 141 of Pure and Applied Mathematics. Elsevier, 2004. Google Scholar
  26. S. Schwarz and L. Staiger. Topologies refining the Cantor topology on X^ω. In C. S. Calude and V. Sassone, editors, Theoretical Computer Science - 6th IFIP TC 1/WG 2.2 International Conference, TCS 2010, Held as Part of WCC 2010, Brisbane, Australia, September 20-23, 2010. Proceedings, volume 323 of IFIP Advances in Information and Communication Technology, pages 271-285. Springer, 2010. Google Scholar
  27. V. L. Selivanov. Wadge degrees of ω-languages of deterministic Turing machines. RAIRO-Theoretical Informatics and Applications, 37(1):67-83, 2003. Google Scholar
  28. V. L. Selivanov. Wadge reducibility and infinite computations. Mathematics in Computer Science, 2(1):5-36, 2008. Google Scholar
  29. O. Serre. Games with winning conditions of high Borel complexity. Theoretical Computer Science, 350(2-3):345-372, 2006. Google Scholar
  30. L. Staiger. ω-languages. In Handbook of formal languages, Vol. 3, pages 339-387. Springer, Berlin, 1997. Google Scholar
  31. L. Staiger. On the power of reading the whole infinite input tape. Grammars, 2 (3):247-257, 1999. Google Scholar
  32. K. Wagner. On ω-regular sets. Information and Control, 43(2):123-177, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact