Reproduction de : Thèse de doctorat : Physique nucléaire : Lyon 1 : 2003. / Titre provenant de l'écran titre. 126 réf. bibliogr.

Thèse de doctorat : Informatique : Paris Est : 2008. Thèse de doctorat : Informatique : Université de Saint-Pétersbourg : 2008. / Thèse soutenue en co-tutelle. Titre provenant de l'écran-titre.

Thèse doctorat : Informatique : Rennes 1 : 2009. / Titre provenant de la page du titre du document électronique. Bibliogr. p. [179]-186. Index.

Reproduction de : Thèse doctorat : Génie informatique, automatique et traitement du signal : Reims : 2008. / Titre provenant de l'écran titre. Bibliogr. p. 129-141.

Reproduction de : Thèse de doctorat : Automatique et Informatique industrielle : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3585. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. p. [141]-144. Liste des publications. Index.

These - Faculté des lettres de Paris. / "Bibliographie": p. [609]-616.

Thesis (Ph. D.)--Columbia University, 1929. / Thesis note on label mounted on t.p. Printed in Great Britain. Bibliography: p. 213-226.

Th. État : Philosophie : Paris 4 : 1988. / Bibliogr. p. [217]-228 Notes bibliogr.

Trees are said to be unordered if the order between successor nodes of a given node is not important. Unranked trees are trees which do not have a priori bound on the number of successors of each node of the tree. Unranked and unordered trees are a possible model for semistructured data. The advantage of this model is that it is less dependant on the representation of semistructured data as XML documents, and the drowback is that formalisms (tree automata, logics) for manipulating this kind of trees are generally related with worse complexity results compared with similar formalisms for unranked and ordered trees. Our aim is a theoretical study of some logics for unranked and unordered trees, espetially from the point of view of using it as query languages for semistructured data. Thus, we are interested in the model checking problem and its complexity, in the satisfiability problem and in caracterising the expressive power of these logics. The model checking problem is, given a tree and a logic formula, to decide whether the trees satisfies the formula; model checking is the mecanism used for query evaluation. The satisfiability problem is, given a logic formula, to decide whether this formula admits some models; satisfiability can be used for query optimisation. Finally, caracterisation of the expressive power of a logic is a caracterisation of the kind of properties it can express. We start from a spatial logic which has been introduced as the basis of a query language for semistructured data. This logic is quite expressive and has several kinds of operators. We consider different fragments of this logic. We identify several interesting fragments of the logic for which the satisfiability problem is decidable, when this problem is known to be undecidable for other fragments. We compare fragments of the logic with monadic second order logic on trees and extensions of it. Finally, studying the model checking problem and its complexity allowed us to propose a model checking algorithm and to establish several results on theoretic complexity of model checking for several fragments of the spatial logic.

Partant des travaux séminaux de Boole, Frege et Russell, le mémoire cherche à clarifier l‟enjeu du pluralisme logique à l‟ère de la prolifération des logiques non-classiques et des développements en informatique théorique et en théorie des preuves. Deux chapitres plus « historiques » sont à l‟ordre du jour : (1) le premier chapitre articule l‟absolutisme de Frege et Russell en prenant soin de montrer comment il exclut la possibilité d‟envisager des structures et des logiques alternatives; (2) le quatrième chapitre expose le chemin qui mena Carnap à l‟adoption de la méthode syntaxique et du principe de tolérance, pour ensuite dégager l‟instrumentalisme carnapien en philosophie de la Logique et des mathématiques. Passant par l‟analyse d‟une interprétation intuitive de la logique linéaire, le deuxième chapitre se tourne ensuite vers l‟établissement d‟une forme logico-mathématique de pluralisme logique à l‟aide de la théorie des relations d‟ordre et la théorie des catégories. Le troisième chapitre délimite le terrain de jeu des positions entourant le débat entre monisme et pluralisme puis offre un argument contre la thèse qui veut que le conflit entre logiques rivales soit apparent, le tout grâce à l‟utilisation du point de vue des logiques sous-structurelles. Enfin, le cinquième chapitre démontre que chacune des trois grandes approches au concept de conséquence logique (modèle-théorétique, preuve-théorétique et dialogique) forme un cadre suffisamment général pour établir un pluralisme. Bref, le mémoire est une défense du pluralisme logique. / Starting from the seminal work of Boole, Frege and Russell, the dissertation seeks to clarify the issue of logical pluralism in the era of the proliferation of non-classical logics and the developments in theoretical computer science and proof theory. Two “historical” chapters are scheduled: the first chapter articulate the absolutism of Frege and Russell, taking care to show how it condemns the possibility to consider alternative structures and logics; the fourth chapter describes the path that led Carnap from the adoption of the syntactic method to the formulation of the principle of tolerance, then goes on to display Carnap‟s instrumentalism in philosophy of Logic and mathematics. Opening with the analysis of an intuitive interpretation of linear logic, the second chapter then turns to the establishment of a form of logico-mathematical pluralism with the help of order theory and category theory. The third chapter delineates the playground of revisionism (philosophical positions surrounding the debate between monism and pluralism) and then provides an argument against the thesis that denies the reality of the conflict between rival logics, all this being done by adopting the substructural logic point of view. The fifth chapter shows that each of the three main approaches to the concept of logical consequence (model-theoretic, proof-theoretic and dialogical) supplies a framework sufficiently general to establish pluralism. In short, the dissertation is a defence of logical pluralism.