Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: topological complexity

Sortuj według:

Ogranicz wyniki do:

The Topological Complexity of MSO+U and Related Automata Models

Hummel S., Skrzypczak M.

Fundamenta Informaticae

2012

Vol. 119, nr 1

87-111

This work shows that for each i ∈ω there exists aΣ -hard ωword language definable in Monadic Second Order Logic extended with the unbounding quantifier (MSO+U). This quantifier was introduced by Bojańczyk to express some asymptotic properties. Since it is not hard to see that each language expressible in MSO+U is projective, our finding solves the topological complexity of MSO+U. The result can immediately be transferred from !-words to infinite labelled trees. As a consequence of the topological hardness we note that no alternating automaton with a Borel acceptance condition — or even with an acceptance condition of a bounded projective complexity — can capture all of MSO+U. The same holds for deterministic and nondeterministic automata since they are special cases of alternating ones. We also give exact topological complexities of related classes of languages recognized by nondeterministic ωB-, ωS- and ωBS-automata studied by Bojańczyk and Colcombet. Furthermore, we show that corresponding alternating automata have higher topological complexity than nondeterministic ones— they inhabit all finite levels of the Borel hierarchy. The paper is an extended journal version of [8]. The main theorem of that article is strengthened here.

On Recognizable Tree Languages Beyond the Borel Hierarchy

Finkel O., Simonnet P.

Fundamenta Informaticae

2009

Vol. 95, nr 2/3

287-303

We investigate the topological complexity of non Borel recognizable tree languages with regard to the difference hierarchy of analytic sets. We show that, for each integer n ≥1, there is a D&omega n;(Σ1) -complete tree language Ln accepted by a (non deterministic) Muller tree automaton. On the other hand, we prove that a tree language accepted by an unambiguous Büchi tree automaton must be Borel. Then we consider the game tree languages W(l,k), for Mostowski-Rabin indices (, k). We prove that the D&omega n;(Σ1) -complete tree languages Ln are Wadge reducible to the game tree languageW(l,k) for k-l≥2. In particular these languagesW(l,k) are not in any class D&omega n;(Σ1) for α<ωω

An ω-Power of a Finitary Language Which is a Borel Set of Infinite Rank

Finkel O.

Fundamenta Informaticae

2004

Vol. 62, nr 3,4

333--342

ω-powers of finitary languages are ω-languages s in the form Vω, where V is a finitary language over a finite alphabet Σ. Since the set Σ,sup>ω of infinite words over Σ can be equipped with the usual Cantor topology, the question of the topological complexity of ω-powers naturally arises and has been raised by Niwinski [13], by Simonnet [15], and by Staiger [18]. It has been proved in [4] that for each integer n ≥ 1, there exist some ω-powers of context free languages which are Πn0-complete Borel sets, and in [5] that there exists a context free language L such that Lω is analytic but not Borel. But the question was still open whether there exists a finitary language V such that Vω is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose ω-power is Borel of infinite rank.