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: Cantor topology

Sortuj według:

Ogranicz wyniki do:

Expressing Cardinality Quantifiers in Monadic Second-Order Logic over Trees

Bárány V., Kaiser Ł., Rabinovich A.

Fundamenta Informaticae

2010

Vol. 100, nr 1/4

1-17

We study an extension of monadic second-order logic of order with the uncountability quantifier "there exist uncountably many sets". We prove that, over the class of finitely branching trees, this extension is equally expressive to plain monadic second-order logic of order. Additionally we find that the continuum hypothesis holds for classes of sets definable in monadic second-order logic over finitely branching trees, which is notable for not all of these classes are analytic. Our approach is based on Shelah’s composition method and uses basic results from descriptive set theory. The elimination result is constructive, yielding a decision procedure for the extended logic.

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.