Wyniki wyszukiwania - BazTech

1

On Recognizable Tree Languages Beyond the Borel Hierarchy

Finkel O., Simonnet P.

Fundamenta Informaticae

|

2009

|

Vol. 95, nr 2/3

287-303

EN

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 α<ωω

2

Highly Undecidable Problems about Recognizability by Tiling Systems

Finkel O.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 2

305-323

EN

Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with usual acceptance conditions, such as the Büchi and Muller ones, in [1]. It was proved in [9] that it is undecidable whether a Büchirecognizable language of infinite pictures is E-recognizable (respectively, A-recognizable). We show here that these two decision problems are actually Π1/2/ -complete, hence located at the second level of the analytical hierarchy, and "highly undecidable". We give the exact degree of numerous other undecidable problems for Büchi-recognizable languages of infinite pictures. In particular, the nonemptiness and the infiniteness problems are Σ1/1/ -complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all Π1/2/ -complete. It is also Π1/2/ -complete to determine whether a given Büchi recognizable language of infinite pictures can be accepted row by row using an automaton model over ordinal words of length ω2/.

3

On Winning Conditions of High Borel Complexity in Pushdown Games

Finkel O.

Fundamenta Informaticae

|

2005

|

Vol. 66, nr 3

277--298

EN

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.

4

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

EN

ω-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.