5 found
Sort by:
  1.  12 DLs
    Olivier Chapuis, Ehud Hrushovski, Pascal Koiran & Bruno Poizat (2002). La Limite Des Theories de Courbes Generiques. Journal of Symbolic Logic 67 (1):24-34.
    Ne estas prima orda formulo, kiu definas la Zariskijajn slositojn inter la konstruitoj, malpli ke la konektojn inter la slositoj.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  2.  9 DLs
    Pascal Koiran (2003). The Theory of Liouville Functions. Journal of Symbolic Logic 68 (2):353-365.
    A Liouville function is an analytic function $H : C \rightarrow C$ with a Taylor series $\Sigma_{n=1}^\infty x^n/a_n$ such the $a_n\prime s$ form a "very fast growing" sequence of integers. In this paper we exhibit the complete first-order theory of the complex field expanded with H.
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  3.  5 DLs
    Olivier Chapuis & Pascal Koiran (1999). Definability of Geometric Properties in Algebraically Closed Fields. Mathematical Logic Quarterly 45 (4):533-550.
    We prove that there exists no sentence F of the language of rings with an extra binary predicat I2 satisfying the following property: for every definable set X ⊆ ℂ2, X is connected if and only if ⊧ F, where I2 is interpreted by X. We conjecture that the same result holds for closed subset of ℂ2. We prove some results motivated by this conjecture.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  4.  2 DLs
    Olivier Chapuis & Pascal Koiran (1999). Saturation and Stability in the Theory of Computation Over the Reals. Annals of Pure and Applied Logic 99 (1-3):1-49.
    This paper was motivated by the following two questions which arise in the theory of complexity for computation over ordered rings in the now famous computational model introduced by Blum, Shub and Smale: 1. is the answer to the question P = ?NP the same in every real-closed field?2. if P ≠ NP for , does there exist a problem of which is NP but neither P nor NP-complete ?Some unclassical complexity classes arise naturally in the study of these questions. (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5.  1 DLs
    Pascal Koiran & Natacha Portier (2001). Back-and-Forth Systems for Generic Curves and a Decision Algorithm for the Limit Theory. Annals of Pure and Applied Logic 111 (3):257-275.
    It was recently shown that the theories of generic algebraic curves converge to a limit theory as their degrees go to infinity. In this paper we give quantitative versions of this result and other similar results. In particular, we show that generic curves of degree higher than 22r cannot be distinguished by a first-order formula of quantifier rank r. A decision algorithm for the limit theory then follows easily. We also show that in this theory all formulas are equivalent to (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation