The goal of this thesis is the study of a harmonious way to combine any first order theory with the theory of finite or infinite trees. For that: First of all, we introduce two classes of theories that we call \emph{infinite-decomposable} and \emph{zero-infinite-decomposable}. We show that these theories are complete and accept a decision procedure which for every proposition gives either $\vrai$ or $\faux$. We show also that these classes of theories contain a large number of fundamental theories used in computer science, we can cite for example: the theory of additive rational or real numbers, the theory of the linear dense order without endpoints, the theory of finite or infinite trees, the construction of trees on an ordered set, and a combination of trees and ordered additive rational or real numbers. We give then an automatic way to combine any first order theory $T$ with the theory of finite or infinite trees. A such hybrid theory is called \emph{extension into trees} of the theory $T$ and is denoted by $T^*$. After having defined the axiomatization of $T^*$ using those of $T$, we define a new class of theories that we call \emph{flexible} and show that if $T$ is flexible then $T^*$ is zero-infinite-decomposable and thus complete. The flexible theories are first order theories having elegant properties which enable us to handle easily first order formulas. We show among other theories that the theory $\add$ of ordered additive rational numbers is flexible and thus that the extension into trees $\addd$ of $\add$ is complete. Finally, we end this thesis by a general algorithm for solving efficiently first order constraints in $\addd$. The algorithm is given in the form of 28 rewriting rules which transform every formula $\varphi$, which can possibly contain free variables, into a disjunction $\phi$ of solved formulas equivalent to $\varphi$ in $\addd$ and such that $\phi$ is either the formula $\vrai$, or the formula $\faux$, or a formula having at least one free variable and being equivalent neither to $\vrai$ nor to $\faux$ in $\addd$. Moreover, the solutions of the free variables of $\phi$ are expressed in a clear and explicit way in $\phi$.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00474384 |
| Date | 15 June 2006 |
| Creators | Djelloul, Khalil |
| Publisher | Université de la Méditerranée - Aix-Marseille II |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | English |
| Type | PhD thesis |
Page generated in 0.0024 seconds