ON INFINITE REAL TRACE RATIONAL LANGUAGES OF MAXIMUM TOPOLOGICAL COMPLEXITY

    loading  Checking for direct PDF access through Ovid

Abstract

We consider the set ℝω(Γ, D) of infinite real traces, over a dependence alphabet (Γ,D) with no isolated letter, equipped with the topology induced by the prefix metric. We prove that all rational languages of infinite real traces are analytic sets. We also reprove that there exist some rational languages of infinite real traces that are analytic but non-Borel sets; in fact, these sets are even Σ11-complete, hence have maximum possible topological complexity. For this purpose, we give an example of a Σ11-complete language that is fundamentally different from the known example of a Σ11-complete infinitary rational relation given by Finkel (2003). Bibliography: 35 titles.

Related Topics

    loading  Loading Related Articles