Nous menons, dans le cadre de la grammaire générative chomskienne, une analyse formelle des énoncés ramifiés du langage naturel ( « La plupart des linguistes et la plupart des philosophes s'apprécient »). Ces énoncés présentent des quantificateurs non linéairement dépendants, qui doivent être traités « en parallèle », alors que leur ordre d'apparition en surface est nécessairement linéaire. Ce phénomène est connu en logique sous le nom de ramification (‘branching quantification') ; en grammaire générative il se traduit par des exigences contradictoires au niveau de la relation de c-commande : symétrie par l'absence de c-commande entre constituants quantifiés au niveau de la forme logique (‘LF') et antisymétrie par la relation de c commande asymétrique au niveau de la forme de surface (en acceptant l'axiome de correspondance linéaire ‘LCA' de Kayne). Pour sortir de cette impasse nous introduisons un nouveau type d'objets que nous avons nommés objets doubles. Les objets doubles créent localement des îlots non linéaires qui permettent d'obtenir la linéarité recherchée en surface sans induire de dépendance au niveau de la forme logique. Leur introduction est justifiée par ailleurs par le traitement qu'ils permettent de la coordination, un phénomène étroitement lié à la ramification. Grâce aux objets doubles tous les types de ramification, avec ou sans coordination, reçoivent une représentation adéquate, menant à une interprétation correcte. Nous résultats trouvent également une application en logique modale épistémique, et pour la représentation de l'interrogation multiple. / We carry out, within the framework of Chomskian generative grammar, a formal analysis of branching sentences in natural language (“Most linguists and most philosophers appreciate each other”). These sentences present quantifiers that are not linearly dependent, which must be treated "in parallel", whereas their surface order is necessarily linear. This phenomenon is known in logic as branching quantification. In generative grammar, branching quantification leads to contradictory requirements on the c-command relation: on the one hand, because of the absence of c-command between quantified constituents, one should have symmetry at LF; on the other hand, accepting Kayne's Linear Correspondence Axiom LCA, one should have antisymmetry of c-command at PF. To leave this dead end we introduce a new type of objects which we named twin objects (‘objets doubles' in French). Twin objects locally create nonlinear islands which make it possible to obtain the expected linearity at the surface without inducing dependence at the level of Logical Form. Their introduction is moreover justified by the treatment of coordination they allow, a phenomenon closely related to branching. Thanks to twin objects all types of branching, with or without coordination, receive an adequate representation, leading to a correct interpretation. Our results also find applications in epistemic modal logic and in the representation of multiple wh-questions.

Various forms of information integration have become ubiquitous in current Business Intelligence (BI) technologies. In many cases, the semantic relationship between heterogeneous data sources is specified using high-level declarative rules, called schema mappings. For decades, Skolem functions have been regarded as an important tool in schema mappings as they permit a precise representation of incomplete information. The powerful mapping language of second-order tuple generating dependencies (SO tgds) permits arbitrary Skolem functions and has been proven to be the right class for modeling many integration problems, such as composition and correlation of mappings. This language is strictly more powerful than the languages used in many integration systems, including source-to-target and nested tgds which are both first-order (FO) languages (commonly known as GLAV and nested GLAV mappings). An important class of GLAV mappings are Local-As-View (LAV) tgds, which has found important application in data integration. These FO mapping languages are known to have more desirable programmatic and computational properties. In this thesis, we present a number of techniques for translating some SO tgds into equivalent, more manageable FO schema mappings. Our results rely on understanding and controlling the presence of incompleteness in mappings. We show that the composition of LAV mappings is not only FO, but can always be expressed as a LAV mapping. As a byproduct, we show that the problem of recovery checking for LAV mappings becomes tractable, in contrast to the case of GLAV mappings for which it is known to be undecidable. We introduce two approaches for transforming SO tgds into equivalent nested GLAV mappings. Our approach considers the presence of source constraints, and provides sufficient conditions for when the rich Skolem functions in SO tgds are well-behaved and have an FO semantics. We experimentally show that these conditions are able to handle a very large number of real schema mappings. Last, we propose a first-step for embracing incompleteness in the context of BI applications. Specifically, we present elements of a formal framework for vivifying data with respect to a business model. We view the task of discovering data-to-business interpretations as one of removing incompleteness from these mappings.

Various forms of information integration have become ubiquitous in current Business Intelligence (BI) technologies. In many cases, the semantic relationship between heterogeneous data sources is specified using high-level declarative rules, called schema mappings. For decades, Skolem functions have been regarded as an important tool in schema mappings as they permit a precise representation of incomplete information. The powerful mapping language of second-order tuple generating dependencies (SO tgds) permits arbitrary Skolem functions and has been proven to be the right class for modeling many integration problems, such as composition and correlation of mappings. This language is strictly more powerful than the languages used in many integration systems, including source-to-target and nested tgds which are both first-order (FO) languages (commonly known as GLAV and nested GLAV mappings). An important class of GLAV mappings are Local-As-View (LAV) tgds, which has found important application in data integration. These FO mapping languages are known to have more desirable programmatic and computational properties. In this thesis, we present a number of techniques for translating some SO tgds into equivalent, more manageable FO schema mappings. Our results rely on understanding and controlling the presence of incompleteness in mappings. We show that the composition of LAV mappings is not only FO, but can always be expressed as a LAV mapping. As a byproduct, we show that the problem of recovery checking for LAV mappings becomes tractable, in contrast to the case of GLAV mappings for which it is known to be undecidable. We introduce two approaches for transforming SO tgds into equivalent nested GLAV mappings. Our approach considers the presence of source constraints, and provides sufficient conditions for when the rich Skolem functions in SO tgds are well-behaved and have an FO semantics. We experimentally show that these conditions are able to handle a very large number of real schema mappings. Last, we propose a first-step for embracing incompleteness in the context of BI applications. Specifically, we present elements of a formal framework for vivifying data with respect to a business model. We view the task of discovering data-to-business interpretations as one of removing incompleteness from these mappings.

Cette thèse examine quelques approches aux équations diophantiennes, en particulier les connexions entre l’analyse diophantienne et la théorie des corps cyclotomiques.Tout d’abord, nous proposons une introduction très sommaire et rapide aux méthodes d’analyse diophantienne que nous avons utilisées dans notre travail de recherche. Nous rappelons la notion de hauteur et présentons le PGCD logarithmique.Ensuite, nous attaquons une conjecture, formulée par Skolem en 1937, sur une équation diophantienne exponentielle. Pour cette conjecture, soit K un corps de nombres, α1 ,…, αm , λ1 ,…, λm des éléments non-nuls de K, et S un ensemble fini de places de K (qui contient toutes les places infinies), de telle sorte que l’anneau de S-entiers OS = OK,S = {α ∈ K : |α|v ≤ 1 pour les places v ∈/ S}contienne α1 , . . . , αm , λ1 , . . . , λm α1-1 , . . . , αm-1. Pour chaque n ∈ Z, soit A(n)=λ_1 α_1^n+⋯+λ_m α_m^n∈O_S. Skolem a suggéré [SK1] :Conjecture (principe local-global exponentiel). Supposons que pour chaque idéal non-nul a de l’anneau O_S, il existe n ∈ Z tel que A(n) ≡0 mod a. Alors, il existe n ∈ Z tel que A(n)=0.Soit Γ le groupe multiplicatif engendré par α1 ,…, αm. Alors Γ est le produit d’un groupe abélien fini et d’un groupe libre de rang fini. Nous démontrons que cette conjecture est vraie lorsque le rang de Γ est un.Après cela, nous généralisons un résultat précédent de Mourad Abouzaid ([A]). Soit F (X,Y) ∈ Q[X,Y] un Q-polynôme irréductible. En 2008, Mourad Abouzaid [A] a démontré le théorème suivant:Théorème (Abouzaid). Supposons que (0,0) soit un point non-singulier de la courbe plane F(X,Y) = 0. Soit m = degX F, n = degY F, M = max{m, n}. Soit ε tel que 0 < ε < 1. Alors, pour toute solution (α, β) ∈ Q ̅2 de F(X,Y) = 0, nous avons soit max{h(α), h(β)} ≤ 56M8ε−2hp(F) + 420M10ε−2 log(4M),soitmax{|h(α) − nlgcd(α, β)|,|h(β) − mlgcd(α, β)|} ≤ εmax{h(α), h(β)}++ 742M7ε−1hp(F) + 5762M9ε−1log(2m + 2n)Cependant, il a imposé la condition que (0,0) soit un point non-singulier de la courbe plane F(X,Y) = 0. En utilisant des versions quelque peu différentes du lemme “absolu” de Siegel et du lemme d’Eisenstein, nous avons pu lever la condition et démontrer le théorème de façon générale. Nous démontrons le théorème suivant:Théorème. Soit F(X,Y) ∈ Q ̅[X,Y] un polynôme absolument irréductible qui satisfasse F(0,0)=0. Soit m=degX F, n=degY F et r = min{i+j:(∂^(i+j) F)/(∂^i X∂^j Y)(0,0)≠0}. Soit ε tel que 0 < ε < 1. Alors, pour tout (α, β) ∈ Q ̅2 tel que F(α,β) = 0, nous avons soith(α) ≤ 200ε−2mn6(hp(F) + 5)soit|(lgcd(α,β))/r-h(α)/n|≤1/r (εh(α)+4000ε^(-1) n^4 (h_p (F)+log⁡(mn)+1)+30n^2 m(h_p (F)+log⁡(mn) ))Ensuite, nous donnons un aperçu des outils que nous avons utilisés dans les corps cyclotomiques. Nous tentons de développer une approche systématique pour un certain genre d’équations diophantiennes. Nous proposons quelques résultats sur les corps cyclotomiques, les anneaux de groupe et les sommes de Jacobi, qui nous seront utiles pour ensuite décrire l’approche.Finalement, nous développons une application de l’approche précédemment expliquée. Nous considèrerons l’équation diophantienne(1) Xn − 1 = BZn,où B ∈ Z est un paramètre. Définissons ϕ∗(B) := ϕ(rad (B)), où rad (B) est le radical de B, et supposons que(2) (n, ϕ∗(B)) = 1.Pour B ∈ N_(>1) fixé, soit N(B) = {n ∈ N_(>1) | ∃ k > 0 tel que n|ϕ∗(B)}. Si p est un premier impair, nous appellerons CF les conditions combinéesI La conjecture de Vandiver est vraie pour p, c’est-à-dire que le nombre de classe h+ du sous-corps réel maximal du corps cyclotomique Q[ζp ], n’est pas divisible par p.II Nous avons ir(p) < √p − 1, en d’autre mots, il y a au plus √p − 1 entiers impairs k < p tels que le nombre de Bernouilli Bk ≡ 0 mod p. [...] / This thesis examines some approaches to address Diophantine equations, specifically we focus on the connection between the Diophantine analysis and the theory of cyclotomic fields.First, we propose a quick introduction to the methods of Diophantine approximation we have used in this research work. We remind the notion of height and introduce the logarithmic gcd.Then, we address a conjecture, made by Thoralf Skolem in 1937, on an exponential Diophantine equation. For this conjecture, let K be a number field, α1 ,…, αm , λ1 ,…, λm non-zero elements in K, and S a finite set of places of K (containing all the infinite places) such that the ring of S-integersOS = OK,S = {α ∈ K : |α|v ≤ 1 pour les places v ∈/ S}contains α1 , . . . , αm , λ1 , . . . , λm α1-1 , . . . , αm-1. For each n ∈ Z, let A(n)=λ_1 α_1^n+⋯+λ_m α_m^n∈O_S. Skolem suggested [SK1] :Conjecture (exponential local-global principle). Assume that for every non zero ideal a of the ring O_S, there exists n ∈ Z such that A(n) ≡0 mod a. Then, there exists n ∈ Z such that A(n)=0.Let Γ be the multiplicative group generated by α1 ,…, αm. Then Γ is the product of a finite abelian group and a free abelian group of finite rank. We prove that the conjecture is true when the rank of Γ is one.After that, we generalize a result previously published by Abouzaid ([A]). Let F(X,Y) ∈ Q[X,Y] be an irreducible Q-polynomial. In 2008, Abouzaid [A] proved the following theorem:Theorem (Abouzaid). Assume that (0,0) is a non-singular point of the plane curve F(X,Y) = 0. Let m = degX F, n = degY F, M = max{m, n}. Let ε satisfy 0 < ε < 1. Then for any solution (α,β) ∈ Q ̅2 of F(X,Y) = 0, we have eithermax{h(α), h(β)} ≤ 56M8ε−2hp(F) + 420M10ε−2 log(4M),ormax{|h(α) − nlgcd(α, β)|,|h(β) − mlgcd(α, β)|} ≤ εmax{h(α), h(β)}++ 742M7ε−1hp(F) + 5762M9ε−1log(2m + 2n)However, he imposed the condition that (0, 0) be a non-singular point of the plane curve F(X,Y) = 0. Using a somewhat different version of Siegel’s “absolute” lemma and of Eisenstein’s lemma, we could remove the condition and prove it in full generality. We prove the following theorem:Theorem. Let F(X,Y) ∈ Q ̅[X,Y] be an absolutely irreducible polynomial satisfying F(0,0)=0. Let m=degX F, n=degY F and r = min{i+j:(∂^(i+j) F)/(∂^i X∂^j Y)(0,0)≠0}. Let ε be such that 0 < ε < 1. Then, for all (α, β) ∈ Q ̅2 such that F(α,β) = 0, we have eitherh(α) ≤ 200ε−2mn6(hp(F) + 5)or|(lgcd(α,β))/r-h(α)/n|≤1/r (εh(α)+4000ε^(-1) n^4 (h_p (F)+log⁡(mn)+1)+30n^2 m(h_p (F)+log⁡(mn) ))Then, we give an overview of the tools we have used in cyclotomic fields. We try there to develop a systematic approach to address a certain type of Diophantine equations. We discuss on cyclotomic extensions and give some basic but useful properties, on group-ring properties and on Jacobi sums.Finally, we show a very interesting application of the approach developed in the previous chapter. There, we consider the Diophantine equation(1) Xn − 1 = BZn,where B ∈ Z is understood as a parameter. Define ϕ∗(B) := ϕ(rad (B)), where rad (B) is the radical of B, and assume that (2) (n, ϕ∗(B)) = 1.For a fixed B ∈ N_(>1)we let N(B) = {n ∈ N_(>1) | ∃ k > 0 such that n|ϕ∗(B)}. If p is an odd prime, we shall denote by CF the combined condition requiring thatI The Vandiver Conjecture holds for p, so the class number h+ of the maximal real subfield of the cyclotomic field Q[ζp ] is not divisible by p.II We have ir>(p) < √p − 1, in other words, there is at most √p − 1 odd integers k < p such that the Bernoulli number Bk ≡ 0 mod p. [...]

No description available.

In this thesis we study the zeros and asymptotics of sequences that satisfy linear recurrence relations with generally nonconstant coefficients. By the theorem of Skolem-Mahler-Lech, the set of zero terms of a sequence that satisfies a linear recurrence relation with constant coefficients taken from a field of characteristic zero is comprised of the union of finitely many arithmetic progressions together with a finite exceptional set. Further, in the nondegenerate case, we can eliminate the possibility of arithmetic progressions and conclude that there are only finitely many zero terms. For generally nonconstant coefficients, there are generalizations of this theorem due to Bézivin and to Methfessel that imply, under fairly general conditions, that we obtain a finite union of arithmetic progressions together with an exceptional set of density zero. Further, a condition is given under which one can exclude the possibility of arithmetic progressions and obtain a set of zero terms of density zero. In this thesis, it is shown that this condition reduces to the nondegeneracy condition in the case of constant coefficients. This allows for a consistent definition of nondegeneracy valid for generally nonconstant coefficients and a unified result is obtained. The asymptotic theory of sequences that satisfy linear recurrence relations with generally nonconstant coefficients begins with the basic theorems of Poincaré and Perron. There are some generalizations of these theorems that hold in greater generality, but if we restrict the coefficient sequences of our linear recurrences to be polynomials in the index, we obtain full asymptotic expansions of a predictable form for the solution sequences. These expansions can be obtained by applying a transfer method of Flajolet and Sedgewick or, in some cases, by applying a bivariate method of Pemantle and Wilson. In this thesis, these methods are applied to a family of binomial sums and full asymptotic expansions are obtained. The leading terms of the expansions are obtained explicitly in all cases, while in some cases a field containing the asymptotic coefficients is obtained and some divisibility properties for the asymptotic coefficients are obtained using a generalization of a method of Stoll and Haible.

No description available.