|
Zapiski Nauchnykh Seminarov POMI, 2004, Volume 316, Pages 205–223
(Mi znsl733)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
On infinite real trace rational languages of maximum topological complexity
O. Finkela, J.-P. Ressayrea, P. Simonnetb a Université Paris VII – Denis Diderot
b Université de Corse Pasquale Paoli
Abstract:
We consider the set $\mathbb R^{\omega}(\Gamma,D)$ of infinite real traces, over a dependence alphabet $(\Gamma,D)$ with no isolated letter, equipped with the topology induced by the prefix metric. We then prove that all rational languages of infinite real traces are analytic sets. We reprove also that there exist some rational languages of infinite real traces which are analytic but non Borel sets, and even ${\boldsymbol{\Sigma}}^1_1$-complete, hence of maximum possible topological complexity. For that purpose we give an example of $\boldsymbol{\Sigma}^1_1$-complete language which is fundamentally different from the known example of $\boldsymbol{\Sigma}^1_1$-complete infinitary rational relation given in [10].
Received: 26.10.2004
Citation:
O. Finkel, J.-P. Ressayre, P. Simonnet, “On infinite real trace rational languages of maximum topological complexity”, Computational complexity theory. Part IX, Zap. Nauchn. Sem. POMI, 316, POMI, St. Petersburg, 2004, 205–223; J. Math. Sci. (N. Y.), 134:5 (2006), 2435–2444
Linking options:
https://www.mathnet.ru/eng/znsl733 https://www.mathnet.ru/eng/znsl/v316/p205
|
Statistics & downloads: |
Abstract page: | 184 | Full-text PDF : | 63 | References: | 47 |
|