9 found
Order:
  1. 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 (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  4
    The Determinacy of Context-Free Games.Olivier Finkel - 2013 - Journal of Symbolic Logic 78 (4):1115-1134.
    We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by realtime 1-counter Büchi automata is equivalent to the determinacy of analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge ofω-languages accepted by 1-counter Büchi automata is equivalent to the analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automatonand a (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  6
    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   1 citation  
  4.  9
    Infinite Games Specified by 2-Tape Automata.Olivier Finkel - 2016 - Annals of Pure and Applied Logic 167 (12):1184-1212.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  5.  20
    A Hierarchy of Tree-Automatic Structures.Olivier Finkel & Stevo Todorčević - 2012 - Journal of Symbolic Logic 77 (1):350-368.
    We consider ω n -automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length ω n for some integer n ≥ 1. We show that all these structures are ω-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for ω 2 -automatic (resp. ω n -automatic for n > 2) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  6.  13
    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 (7 more)  
     
    Export citation  
     
    Bookmark  
  7.  11
    Local Sentences and Mahlo Cardinals.Olivier Finkel & Stevo Todorcevic - 2007 - Mathematical Logic Quarterly 53 (6):558-563.
    Local sentences were introduced by Ressayre in [6] who proved certain remarkable stretching theorems establishing the equivalence between the existence of finite models for these sentences and the existence of some infinite well ordered models. Two of these stretching theorems were only proved under certain large cardinal axioms but the question of their exact strength was left open in [4]. Here we solve this problem, using a combinatorial result of J. H. Schmerl [7]. In fact, we show that the stretching (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  8.  3
    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 (4 more)  
     
    Export citation  
     
    Bookmark  
  9.  3
    The Wadge Hierarchy of Petri Nets Ω-Languages.Jean-Pierre Ressayre, Olivier Finkel & Jacques Duparc - 2014 - In Dieter Spreen, Hannes Diener & Vasco Brattka (eds.), Logic, Computation, Hierarchies. De Gruyter. pp. 109-138.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark