Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Borel complexity

Sortuj według:

Ogranicz wyniki do:

Universal sets for ideals

Cieślak A., Michalski M.

Bulletin of the Polish Academy of Sciences. Mathematics

2018

Vol. 66, no. 2

157--166

We consider the notion of universal sets for ideals. We show that there exist universal sets of minimal Borel complexity for classical ideals like the null subsets of 2ω and the meager subsets of any Polish space, and demonstrate that the existence of such sets is helpful in establishing some facts about the real line in generic extensions. We also construct universal sets for E, the σ-ideal generated by closed null subsets of 2ω, and for some ideals connected with forcing notions: the Kσ subsets of ωω and the Laver ideal. We also consider Fubini products of ideals and show that there are Σ03 universal sets for N[symbol]M and M[symbol]N.

On Winning Conditions of High Borel Complexity in Pushdown Games

Finkel O.

Fundamenta Informaticae

2005

Vol. 66, nr 3

277--298

In a recent paper [19,20] Serre has presented some decidable winning conditions [...] of arbitrarily high finite Borel complexity for games on finite graphs or on pushdown graphs. We answer in this paper several questions which were raised by Serre in [19,20]. We study classes \mathbbCn(A), defined in [20], and show that these classes are included in the class of non-ambiguous context free w-languages. Moreover from the study of a larger class \mathbbCln(A) we infer that the complements of languages in \mathbbCn(A) are also non-ambiguous context free w-languages. We conclude the study of classes \mathbbCn(A) by showing that they are neither closed under union nor under intersection. We prove also that there exists pushdown games, equipped with winning conditions in the form [...], where the winning sets are not deterministic context free languages, giving examples of winning sets which are non-deterministic non-ambiguous context free languages, inherently ambiguous context free languages, or even non context free languages.