ﻻ يوجد ملخص باللغة العربية
The $omega$-power of a finitary language L over a finite alphabet $Sigma$ is the language of infinite words over $Sigma$ defined by L $infty$ := {w 0 w 1. .. $in$ $Sigma$ $omega$ | $forall$i $in$ $omega$ w i $in$ L}. The $omega$-powers appear very naturally in Theoretical Computer Science in the characterization of several classes of languages of infinite words accepted by various kinds of automata, like B{u}chi automata or B{u}chi pushdown automata. We survey some recent results about the links relating Descriptive Set Theory and $omega$-powers.
Omega-powers of finitary languages are omega languages in the form V^omega, where V is a finitary language over a finite alphabet X. Since the set of infinite words over X can be equipped with the usual Cantor topology, the question of the topologica
Locally finite omega languages were introduced by Ressayre in [Journal of Symbolic Logic, Volume 53, No. 4, p.1009-1026]. They generalize omega languages accepted by finite automata or defined by monadic second order sentences. We study here closure
We study the links between the topological complexity of an omega context free language and its degree of ambiguity. In particular, using known facts from classical descriptive set theory, we prove that non Borel omega context free languages which ar
We prove that $omega$-languages of (non-deterministic) Petri nets and $omega$-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of $omega$-languages of (non-determinist
Werners set-theoretical model is one of the simplest models of CIC. It combines a functional view of predicative universes with a collapsed view of the impredicative sort Prop. However this model of Prop is so coarse that the principle of excluded mi