اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAn omega-Power of a Finitary Language Which is a Borel Set of Infinite Rank
112
0
0.0
(
0
)
تأليف
Olivier Finkel
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 topological complexity of omega-powers naturally arises and has been raised by Niwinski, by Simonnet, and by Staiger. It has been recently proved that for each integer n > 0, there exist some omega-powers of context free languages which are Pi^0_n-complete Borel sets, and that there exists a context free language L such that L^omega is analytic but not Borel. But the question was still open whether there exists a finitary language V such that V^omega is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose omega-power is Borel of infinite rank.
قيم البحث
اقرأ أيضاً
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 na
turally 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.
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
ddle holds. Following our previous work, we interpret Prop into a topological space (a special case of Heyting algebra) to make the model more intuitionistic without sacrificing simplicity. We improve on that work by providing a full interpretation of dependent product types, using Alexandroff spaces. We also extend our approach to inductive types by adding support for lists.
We prove that, for any natural number n $ge$ 1, we can find a finite alphabet $Sigma$ and a finitary language L over $Sigma$ accepted by a one-counter automaton, such that the $omega$-power L $infty$ := {w 0 w 1. .. $in$ $Sigma$ $omega$ | $forall$i $
in$ $omega$ w i $in$ L} is $Pi$ 0 n-complete. We prove a similar result for the class $Sigma$ 0 n .
We show that the set of absolutely normal numbers is $mathbf Pi^0_3$-complete in the Borel hierarchy of subsets of real numbers. Similarly, the set of absolutely normal numbers is $Pi^0_3$-complete in the effective Borel hierarchy.
Escalation in games is when agents keep playing forever. Based on formal proofs we claim that if agents assume that resource are infinite, escalation is rational.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
