DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2017.22

Polishness of Some Topologies Related to Automata

Authors: Olivier Carton, Olivier Finkel, and Dominique Lecomte

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{carton_et_al:LIPIcs.CSL.2017.22,
  author =	{Carton, Olivier and Finkel, Olivier and Lecomte, Dominique},
  title =	{{Polishness of Some Topologies Related to Automata}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.22},
  URN =		{urn:nbn:de:0030-drops-76728},
  doi =		{10.4230/LIPIcs.CSL.2017.22},
  annote =	{Keywords: Automata and formal languages; logic in computer science; infinite words; B\"{u}chi automaton; regular omega-language; Cantor space; finer topologies; B\"{u}c}
}

Document

DOI: 10.4230/DagSemProc.08271.7

Topological Complexity of omega-Powers: Extended Abstract

Authors: Olivier Finkel and Dominique Lecomte

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)

Abstract

The operation of taking the omega-power $V^omega$ of a language $V$ is a fundamental operation over finitary languages leading to omega-languages. Since the set $X^omega$ of infinite words over a finite alphabet $X$ can be equipped with the usual Cantor topology, the question of the topological complexity of omega-powers of finitary languages naturally arises and has been posed by Damian Niwinski (1990), Pierre Simonnet (1992), and Ludwig Staiger (1997). We investigate the topological complexity of omega-powers. We prove the following very surprising results which show that omega-powers exhibit a great opological complexity: for each non-null countable ordinal $xi$, there exist some $Sigma^0_xi$-complete omega-powers, and some $Pi^0_xi$-complete omega-powers. On the other hand, the Wadge hierarchy is a great refinement of the Borel hierarchy, determined by Bill Wadge. We show that, for each ordinal $xi$ greater than or equal to 3, there are uncountably many Wadge degrees of omega-powers of Borel rank $xi +1$. Using tools of effective descriptive set theory, we prove some effective versions of the above results.

Cite as

Olivier Finkel and Dominique Lecomte. Topological Complexity of omega-Powers: Extended Abstract. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{finkel_et_al:DagSemProc.08271.7,
  author =	{Finkel, Olivier and Lecomte, Dominique},
  title =	{{Topological Complexity of omega-Powers: Extended Abstract}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.7},
  URN =		{urn:nbn:de:0030-drops-16505},
  doi =		{10.4230/DagSemProc.08271.7},
  annote =	{Keywords: Infinite words, omega-languages, omega-powers, Cantor topology, topological complexity, Borel sets, Borel ranks, complete sets, Wadge hierarchy, Wadge}
}

Search Results

Documents authored by Lecomte, Dominique

Polishness of Some Topologies Related to Automata

Abstract

Cite as

Topological Complexity of omega-Powers: Extended Abstract

Abstract

Cite as

Thanks for your feedback!

Could not send message