Local sentences and the formal languages they define were introduced by Ressayre in. We prove that locally finite ω‐languages and effective analytic sets have the same topological complexity: the Borel and Wadge hierarchies of the class of locally finite ω‐languages are equal to the Borel and Wadge hierarchies of the class of effective analytic sets. In particular, for each non‐null recursive ordinal there exist some ‐complete and some ‐complete locally finite ω‐languages, and the supremum of the set of Borel ranks (...) of locally finite ω‐languages is the ordinal, which is strictly greater than the first non‐recursive ordinal. This gives an answer to the question of the topological complexity of locally finite ω‐languages, which was asked by Simonnet and also by Duparc, Finkel, and Ressayre in. Moreover we show that the topological complexity of a locally finite ω‐language defined by a local sentence φ may depend on the models of the Zermelo‐Fraenkel axiomatic system. Using similar constructions as in the proof of the above results we also show that the equivalence, the inclusion, and the universality problems for locally finite ω‐languages are ‐complete, hence highly undecidable. (shrink)

Louveau showed that if a Borel set in a Polish space happens to be in a Borel Wadge class $$\Gamma $$, then its $$\Gamma $$ -code can be obtained from its Borel code in a hyperarithmetical manner. We extend Louveau’s theorem to Borel functions: If a Borel function on a Polish space happens to be a $$ \underset{\widetilde{}}{\varvec{\Sigma }}\hbox {}_t$$ -function, then one can find its $$ \underset{\widetilde{}}{\varvec{\Sigma }}\hbox {}_t$$ -code hyperarithmetically relative to its Borel code. More generally, we prove (...) extension-type, domination-type, and decomposition-type variants of Louveau’s theorem for Borel functions. (shrink)

Every computable function has to be continuous. To develop computability theory of discontinuous functions, we study low levels of the arithmetical hierarchy of nonuniformly computable functions on Baire space. First, we classify nonuniformly computable functions on Baire space from the viewpoint of learning theory and piecewise computability. For instance, we show that mind-change-bounded learnability is equivalent to finite View the MathML source2-piecewise computability 2 denotes the difference of two View the MathML sourceΠ10 sets), error-bounded learnability is equivalent to finite View (...) the MathML sourceΔ20-piecewise computability, and learnability is equivalent to countable View the MathML sourceΠ10-piecewise computability . Second, we introduce disjunction-like operations such as the coproduct based on BHK-like interpretations, and then, we see that these operations induce Galois connections between the Medvedev degree structure and associated Medvedev/ Muchnik-like degree structures. Finally, we interpret these results in the context of the Weihrauch degrees and Wadge-like games. (shrink)

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Π10 subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty Π10 subsets of Cantor space, we show the existence of a finite-Δ20-piecewise degree containing infinitely many finite-2-piecewise degrees, and a finite-2-piecewise degree containing infinitely many finite-Δ20-piecewise degrees 2 denotes the difference of two Πn0 sets), whereas the greatest degrees in (...) these three “finite-Γ-piecewise” degree structures coincide. Moreover, as for nonempty Π10 subsets of Cantor space, we also show that every nonzero finite-2-piecewise degree includes infinitely many Medvedev degrees, every nonzero countable-Δ20-piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite-2-countable-Δ20-piecewise degree includes infinitely many countable-Δ20-piecewise degrees, and every nonzero Muchnik degree includes infinitely many finite-2-countable-Δ20-piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable-Δ20-piecewise degree of a nonempty Π10 subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev degree structure and the finite-Γ-piecewise degree structure of all subsets of Baire space by showing that none of the finite-Γ-piecewise structures is Brouwerian, where Γ is any of the Wadge classes mentioned above. (shrink)

Locally finite omega languages were introduced by Ressayre [Formal languages defined by the underlying structure of their words. J Symb Log 53(4):1009–1026, 1988]. These languages are defined by local sentences and extend ω-languages accepted by Büchi automata or defined by monadic second order sentences. We investigate their topological complexity. All locally finite ω-languages are analytic sets, the class LOC ω of locally finite ω-languages meets all finite levels of the Borel hierarchy and there exist some locally finite ω-languages which are (...) Borel sets of infinite rank or even analytic but non-Borel sets. This gives partial answers to questions of Simonnet (Automates et Théorie Descriptive, Ph.D. Thesis. Université Paris 7, March 1992) and of Duparc et al. [Computer science and the fine structure of Borel sets. Theor Comput Sci 257(1–2):85–105, 2001]. (shrink)

We prove that, for any natural number \, we can find a finite alphabet \ and a finitary language L over \ accepted by a one-counter automaton, such that the \-power $$\begin{aligned} L^\infty :=\{ w_0w_1\ldots \in \Sigma ^\omega \mid \forall i\in \omega ~~w_i\in L\} \end{aligned}$$is \-complete. We prove a similar result for the class \.

A dictionary is a set of finite words over some finite alphabet X. The omega-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [Omega-powers and descriptive set theory, JSL 2005] the complexity of the set of dictionaries whose associated omega-powers have a given complexity. In particular, he considered the sets $W({bfSi}^0_{k})$ (respectively, $W({bfPi}^0_{k})$, $W({bfDelta}_1^1)$) of dictionaries $V subseteq 2^star$ whose omega-powers are ${bfSi}^0_{k}$-sets (respectively, ${bfPi}^0_{k}$-sets, Borel sets). In (...) this paper we first establish a new relation between the sets $W({bfSigma}^0_{2})$ and $W({bfDelta}_1^1)$, showing that the set $W({bfDelta}_1^1)$ is ``more complex' than the set $W({bfSigma}^0_{2})$. As an application we improve the lower bound on the complexity of $W({bfDelta}_1^1)$ given by Lecomte. Then we prove that, for every integer $kgeq 2$, (respectively, $kgeq 3$) the set of dictionaries $W({bfPi}^0_{k+1})$ (respectively, $W({bfSi}^0_{k+1})$) is ``more complex' than the set of dictionaries $W({bfPi}^0_{k})$ (respectively, $W({bfSi}^0_{k})$). (shrink)

We prove that, for each countable ordinal ξ≥1, there exist some -complete ω-powers, and some -complete ω-powers, extending previous works on the topological complexity of ω-powers [O. Finkel, Topological properties of omega context free languages, Theoretical Computer Science 262 669–697; O. Finkel, Borel hierarchy and omega context free languages, Theoretical Computer Science 290 1385–1405; O. Finkel, An omega-power of a finitary language which is a borel set of infinite rank, Fundamenta informaticae 62 333–342; D. Lecomte, Sur les ensembles de phrases (...) infinies constructibles a partir d’un dictionnaire sur un alphabet fini, Séminaire d’Initiation a l’Analyse, 1, année 2001–2002; D. Lecomte, Omega-powers and descriptive set theory, Journal of Symbolic Logic 70 1210–1232; J. Duparc, O. Finkel, An ω-Power of a Context-Free Language Which Is Borel Above , in: S. Bold, B. Löwe, T. Räsch, J. van Benthem , in the Proceedings of the international conference foundations of the formal sciences V : Infinite Games, November 26th to 29th, 2004, Bonn, Germany, in: Studies in Logic, vol. 11, College Publications at King’s College, 2007, pp. 109–122]. We prove effective versions of these results; in particular, for each recursive ordinal there exist some recursive sets A2<ω such that , where and denote classes of the hyperarithmetical hierarchy. To do this, we prove effective versions of a result by Kuratowski, describing a set as the range of a closed subset of the Baire space ωω by a continuous bijection. This leads us to prove closure properties for the pointclasses in arbitrary recursively presented Polish spaces. We apply our existence results to get better computations of the topological complexity of some sets of dictionaries considered in [D. Lecomte, Omega-powers and descriptive set theory, Journal of Symbolic Logic 70 1210–1232]. (shrink)

We present a self‐contained analysis of some reduction games, which characterise various natural subclasses of the first Baire class of functions ranging from and into 0‐dimensional Polish spaces. We prove that these games are determined, without using Martin's Borel determinacy, and give precise descriptions of the winning strategies for Player I. As an application of this analysis, we get a new proof of the Baire's lemma on pointwise convergence.

We provide a game theoretical proof of the fact that if f is a function from a zero-dimensional Polish space to \ that has a point of continuity when restricted to any non-empty compact subset, then f is of Baire class 1. We use this property of the restrictions to compact sets to give a generalisation of Baire’s grand theorem for functions of any Baire class.

We obtain several game characterizations of Baire 1 functions between Polish spaces _X_, _Y_ which extends the recent result of V. Kiss. Then we propose similar characterizations for equi-Bare 1 families of functions. Also, using related ideas, we give game characterizations of Baire measurable and Lebesgue measurable functions.