Switch to: References

Add citations

You must login to add citations.
  1. Some Remarks on Baire’s Grand Theorem.Riccardo Camerlo & Jacques Duparc - 2018 - Archive for Mathematical Logic 57 (3-4):195-201.
    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.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Game Representations of Classes of Piecewise Definable Functions.Luca Motto Ros - 2011 - Mathematical Logic Quarterly 57 (1):95-112.
    We present a general way of defining various reduction games on ω which “represent” corresponding topologically defined classes of functions. In particular, we will show how to construct games for piecewise defined functions, for functions which are pointwise limit of certain sequences of functions and for Γ-measurable functions. These games turn out to be useful as a combinatorial tool for the study of general reducibilities for subsets of the Baire space [10].
    No categories
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Topological Complexity of Locally Finite Ω-Languages.Olivier Finkel - 2008 - Archive for Mathematical Logic 47 (6):625-651.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Some Complete $$\omega $$-Powers of a One-Counter Language, for Any Borel Class of Finite Rank.Olivier Finkel & Dominique Lecomte - 2021 - Archive for Mathematical Logic 60 (1-2):161-187.
    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 \.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • On Some Sets of Dictionaries Whose Ω ‐Powers Have a Given.Olivier Finkel - 2010 - Mathematical Logic Quarterly 56 (5):452-460.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  • Locally Finite Ω-Languages and Effective Analytic Sets Have the Same Topological Complexity.Olivier Finkel - 2016 - Mathematical Logic Quarterly 62 (4-5):303-318.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Inside the Muchnik Degrees I: Discontinuity, Learnability and Constructivism.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (5):1058-1114.
    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 (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Playing in the First Baire Class.Raphaël Carroy - 2014 - Mathematical Logic Quarterly 60 (1-2):10.
  • Classical and Effective Descriptive Complexities of Ω-Powers.Olivier Finkel & Dominique Lecomte - 2009 - Annals of Pure and Applied Logic 160 (2):163-191.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Inside the Muchnik Degrees II: The Degree Structures Induced by the Arithmetical Hierarchy of Countably Continuous Functions.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (6):1201-1241.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation