Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDescriptive Set Theory and $omega$-Powers of Finitary Languages
260
0
0.0
(
0
)
Added by
Olivier Finkel
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Olivier Finkel
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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 properties of the family LOC_omega of locally finite omega languages. In particular we show that the class LOC_omega is neither closed under intersection nor under complementation, giving an answer to a question of Ressayre.
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 are recognized by Buchi pushdown automata have a maximum degree of ambiguity. This result implies that degrees of ambiguity are really not preserved by the operation of taking the omega power of a finitary context free language. We prove also that taking the adherence or the delta-limit of a finitary language preserves neither unambiguity nor inherent ambiguity. On the other side we show that methods used in the study of omega context free languages can also be applied to study the notion of ambiguity in infinitary rational relations accepted by Buchi 2-tape automata and we get first results in that direction.
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-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of $omega$-languages of (non-deterministic) Turing machines which also form the class of effective analytic sets. In particular, for each non-null recursive ordinal $alpha < omega_1^{{rm CK}} $ there exist some ${bf Sigma}^0_alpha$-complete and some ${bf Pi}^0_alpha$-complete $omega$-languages of Petri nets, and the supremum of the set of Borel ranks of $omega$-languages of Petri nets is the ordinal $gamma_2^1$, which is strictly greater than the first non-recursive ordinal $omega_1^{{rm CK}}$. We also prove that there are some ${bf Sigma}_1^1$-complete, hence non-Borel, $omega$-languages of Petri nets, and that it is consistent with ZFC that there exist some $omega$-languages of Petri nets which are neither Borel nor ${bf Sigma}_1^1$-complete. This answers the question of the topological complexity of $omega$-languages of (non-deterministic) Petri nets which was left open in [DFR14,FS14].
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 middle 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
