On Infinite Real Trace Rational Languages of Maximum Topological Complexity
Finkel, Olivier ; Ressayre, Jean-Pierre ; Simonnet, Pierre
HAL, hal-00109918 / Harvested from HAL
Text on HAL
We consider the set 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 and that there exist some rational languages of infinite real traces which are analytic but non Borel sets, and even Sigma^1_1-complete, hence of maximum possible topological complexity.
Publié le : 2004-07-05
Classification:  Real traces,  rational languages,  topological properties,  analytic and Borel sets,  [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO],  [MATH.MATH-LO]Mathematics [math]/Logic [math.LO] 
@article{hal-00109918,
     author = {Finkel, Olivier and Ressayre, Jean-Pierre and Simonnet, Pierre},
     title = {On Infinite Real Trace Rational Languages of Maximum Topological Complexity},
     journal = {HAL},
     volume = {2004},
     number = {0},
     year = {2004},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00109918}
}

Finkel, Olivier; Ressayre, Jean-Pierre; Simonnet, Pierre. On Infinite Real Trace Rational Languages of Maximum Topological Complexity. HAL, Tome 2004 (2004) no. 0, . http://gdmltest.u-ga.fr/item/hal-00109918/