RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2004 Volume 316, Pages 205–223 (Mi znsl733)

This article is cited 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].

UDC: 510.52+519.16

Received: 26.10.2004

Language: English


 English version:
Journal of Mathematical Sciences (New York), 2006, 134:5, 2435–2444

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024