|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 2 van 8 gevonden artikelen
| Titel: |
An ?-Power of a Finitary Language Which is a Borel Set of Infinite Rank |
| Auteur: |
Olivier Finkel |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 62 (2004) nr. 3-4 pagina's 333-342 |
| Jaar: |
2004-11-30 |
| Inhoud: |
ω-powers of finitary languages are ω-languages in the form Vω, where V is a finitary language over a finite alphabet Sigma. Since the set Σω 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 [14] 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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 2 van 8 gevonden artikelen
| << vorige | volgende >> |