On Infinite Real Trace Rational Languages of Maximum Topological Complexity

Simple item page
dc.creatorFinkel, Olivier
dc.creatorRessayre, Jean-Pierre
dc.creatorSimonnet, Pierre
dc.date2008-01-03
dc.date.accessioned2026-07-07T08:52:21Z
dc.date.available2026-07-07T08:52:21Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/0801.0537
dc.identifierhttp://arxiv.org/abs/0801.0537
dc.identifierZapiski Nauchnyh Seminarov POMI 316 (2004) 205-223
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/145253
dc.subjectLogic in Computer Science
dc.subjectLogic
dc.titleOn Infinite Real Trace Rational Languages of Maximum Topological Complexity
dc.typetext

Files

Collections

arXiv