Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSome complete $omega$-powers of a one-counter language, for any Borel class of finite rank
104
0
0.0
(
0
)
Added by
Dominique Lecomte
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Olivier Finkel
Ask ChatGPT about the research
No Arabic abstract
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 .
rate research
Read More
We develop general machinery to cast the class of potential canonical Scott sentences of an infinitary sentence $Phi$ as a class of structures in a related language. From this, we show that $Phi$ has a Borel complete expansion if and only if $S_infty$ divides $Aut(M)$ for some countable model $Mmodels Phi$. Using this, we prove that for theories $T_h$ asserting that ${E_n}$ is a countable family of cross cutting equivalence relations with $h(n)$ classes, if $h(n)$ is uniformly bounded then $T_h$ is not Borel complete, providing a converse to Theorem~2.1 of cite{LU}.
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.
We study the extension of the Kechris-Solecki-Todorcevic dichotomy on analytic graphs to dimensions higher than 2. We prove that the extension is possible in any dimension, finite or infinite. The original proof works in the case of the finite dimension. We first prove that the natural extension does not work in the case of the infinite dimension, for the notion of continuous homomorphism used in the original theorem. Then we solve the problem in the case of the infinite dimension. Finally, we prove that the natural extension works in the case of the infinite dimension, but for the notion of Baire-measurable homomorphism.
We study the (parameter) synthesis problem for one-counter automata with parameters. One-counter automata are obtained by extending classical finite-state automata with a counter whose value can range over non-negative integers and be tested for zero. The updates and tests applicable to the counter can further be made parametric by introducing a set of integer-valued variables called parameters. The synthesis problem for such automata asks whether there exists a valuation of the parameters such that all infinite runs of the automaton satisfy some omega-regular property. Lechner showed that (the complement of) the problem can be encoded in a restricted one-alternation fragment of Presburger arithmetic with divisibility. In this work (i) we argue that said fragment, called AERPADPLUS, is unfortunately undecidable. Nevertheless, by a careful re-encoding of the problem into a decidable restriction of AERPADPLUS, (ii) we prove that the synthesis problem is decidable in general and in N2EXP for several fixed omega-regular properties. Finally, (iii) we give a polynomial-space algorithm for the special case of the problem where parameters can only be used in tests, and not updates, of the counter.
We study the class of Borel equivalence relations under continuous reducibility. In particular , we characterize when a Borel equivalence relation with countable equivalence classes is $Sigma$ 0 $xi$ (or $Pi$ 0 $xi$). We characterize when all the equivalence classes of such a relation are $Sigma$ 0 $xi$ (or $Pi$ 0 $xi$). We prove analogous results for the Borel equivalence relations with countably many equivalence classes. We also completely solve these two problems for the first two ranks. In order to do this, we prove some extensions of the Louveau-Saint Raymond theorem which itself generalized the Hurewicz theorem characterizing when a Borel subset of a Polish space is G $delta$ .
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
