To see the other types of publications on this topic, follow the link: Réécriture, Systèmes de (informatique).
Dissertations / Theses on the topic 'Réécriture, Systèmes de (informatique)'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Réécriture, Systèmes de (informatique).'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Chalhoub, Georges. "Réécriture de requêtes mutimédia." Dijon, 2009. http://www.theses.fr/2009DIJOS005.
Full textAbstract:
La recherche d’information subit depuis quelques années une mutation significative liée aux technologies Web et aux dispositifs électroniques personnels qui ont permis à toute personne d’être connectée à la toile à tout moment et depuis pratiquement n’importe quel endroit. Les applications de recherche d’information actuelles se doivent d’adapter son fonctionnement selon l’utilisateur et son contexte, puisque chacun a ses propres besoins, intérêts, contraintes, et préférences. Plusieurs techniques d’adaptation ont vu le jour, en particulier la réécriture de requête permettant de modifier certains prédicats initiaux afin de mieux répondre aux attentes de l’utilisateur. Cependant, la plupart de ces techniques ne sont pas appropriées à la recherche d’information multimédia, de plus en plus produite, partagée, et recherchée par les utilisateurs. Cela est principalement lié: 1-) à la complexité de la description et de la représentation du contenu multimédia pouvant être décrit par des propriétés sémantiques, physiques (couleurs, formes, textures, etc. ), spatiales et temporelles, etc. 2)- à l’ambigüité causée par le pouvoir d’expression des langages d’interrogation proposés pour la recherche d’information multimédia, et 3)- à la prise partielle des préférences de chaque utilisateur. Nous proposons, dans cette thèse, une approche de réécriture de requêtes multimédia qui permet à la fois de considérer la spécificité de chaque propriété multimédia impliquée dans la requête et le profil de l’utilisateur. S’articulant autour du concept de voisinage que nous définissons ici, notre approche comporte trois phases : la pré-réécriture qui permet de définir des voisinages pondérés des valeurs à réécrire, la réécriture brute dans laquelle nous définissons une fonction de relaxation de valeurs et nous intégrons les contraintes de l’utilisateur en appliquant une fonction de contrôle, et la post-réécriture qui a pour mission d’adapter le résultat et le rendre plus pertinent selon les besoins de l’utilisateur. Plusieurs prototypes ont été implémentés ainsi qu’une panoplie de tests expérimentaux ayant été menés dans le but de valider notre proposition.
2
Lombardi, Carlos Alberto. "Espaces de réductions dans les systèmes de réécriture non-séquentiels et les systèmes de réécriture infinitaires." Paris 7, 2014. http://www.theses.fr/2014PA077168.
Full textAbstract:
On aborde dans cette thèse certaines propriétés formelles de systèmes de réécriture qui concernent leurs espaces des dérivations. Les calculs choisis présentent des caractéristiques particulières qui font l'étude des propriétés choisies des défis intéressants. Les contributions les plus importantes de ce travail sont: (1) nous définons une stratégie de réduction multiradicaux pour le Pure Pattern Calculus, un calcul d'ordre supérieur non-séquentiel, et nous prouvons que cette stratégie est normalisante; (2) nous proposons une manière de formaliser le concept de réduction standard pour I Linear Substitution Calculus, un calcul avec substitutions explicites agissent à la distance dont les réductions sont considérés modulo une rélation d'équivalence dans l'ensemble des termes, et nous aboutissons à des résultats d'existence et unicité des reductions standards pour cette formalisation; et (3)nous donnons une charactérisation de l'équivalence entre réductions pour les systèmes de réécriture des termes infinitaires de premier ordre linéares à gauche, et nous nous servons de cette charactérisation pour développer une preuve d'une version renforcée du résultat de compression des réductions infinitaires. Un trait commun a ces trois sujets est l'utilisation de formalismes génériques de systèmes de réécriture. L'étude sur le Pure Pattern Calculus et celui concernant le Linear Substitution Calculus reposent sur le concept de Système Abstrait de Réécriture De son côté, pour le travail sur la réécriture infinitaire, on se sert d'un modèle fondé sur la notion de proof term. Des extensions à ces formalismes génériques sont des contributions additionnelles de cette thèse<br>We study different aspects related to the reduction spaces of diverse rewriting systems. These systems include features which make the study of their reduction spaces a far from trivial task. The main contributions of this thesis are: (1)we define a multistep reduction strategy for the Pure Pattern Calculus, a non-sequential higher-order term rewriting system, and we prove that the defined strategy is normalising;(2)we propose a formalisation of the concept of standard reduction for the Linear Substitution Calculus, a calculus of explicit substitutions whose reductions are considered modulo an equivaience relation defined on the set of terms, and we obtain a result of uniqueness of standard reductions for this formalisation; and finally, (3) we characterise the equivalence of reductions for the infinitary, first-order, left-linear term rewriting systems, and we use this characterisation to develop an alternative proof of the compression result. We remark that we use generic models of rewriting systems: a version of the notion of Abstract Rewriting Systems is used for the study of the Pure Pattern Calculus and the Linear Substitution Calculus, while a model based on the concept of proof terms is used for the study of infinitary rewriting. We include extensions of both used generic models; these extensions can be considered as additional contributions of this thesis
3
Salinier, Bruno. "Simulation de systèmes de réécriture de termes par des systèmes constructeurs." Bordeaux 1, 1995. http://www.theses.fr/1995BOR10643.
Full textAbstract:
Les systemes constructeurs fortement sequentiels admettent une strategie tres efficace pour une suite de reductions. Thatte a decouvert une transformation syntaxique qui permet de simuler tout systeme orthogonal par un systeme constructeur: toute forme normale dans ce nouveau systeme est egalement une forme normale dans le systeme initial. Malheureusement, cette transformation ne conserve pas la forte sequentialite, interdisant l'usage de la strategie efficace pour les systemes fortement sequentiels constructeurs. Dans cette these, nous definissons la classe des systemes equivalents constructeurs pour laquelle la forte sequentialite est conservee ; nous donnons quelques proprietes de cette classe ainsi qu'une caracterisation algebrique. Nous montrons egalement qu'il s'agit d'une sous-classe de la classe des systemes forward-branching definie par strandh qui est elle-meme incluse dans la classe des systemes fortement sequentiels. Ensuite, nous exposons une transformation de notre conception basee sur la notion d'arbre d'index. Cette transformation permet de simuler tout systeme forward-branching par un systeme fortement sequentiel constructeur. Dans le pire des cas, la taille de ce nouveau systeme est quadratique par rapport a la taille du systeme d'origine. Nous ameliorons alors notre transformation afin que la taille du systeme issu de la transformation soit lineaire par rapport a la taille du systeme d'entree
4
Touzet, Hélène. "Propriétés combinatoires pour la terminaison de systèmes de réécriture." Nancy 1, 1997. http://www.theses.fr/1997NAN10295.
Full textAbstract:
Cette thèse s'inscrit dans le cadre général de la preuve de terminaison de systèmes de réécriture, avec un accent particulier sur le problème de la complexité. La terminaison est une propriété indécidable de la théorie de la réécriture. Il existe toutefois un résultat de combinatoire qui fournit un critère suffisant : le théorème de Kruskal. Ce théorème a conduit à la définition d'ordres de terminaison largement utilisés en démonstration automatique. Nous donnons une analyse de la complexité pour ces ordres de terminaison dans le cas des termes ou des mots et nous envisageons quelles en sont les limites. L'approche que nous avons retenue pour cette étude repose sur la théorie des hiérarchies de fonctions indexées par les ordinaux. Un second volet de la thèse est consacré à une extension des hiérarchies de fonctions, avec la définition d'un système alternatif de termes ordinaux. Les opérateurs fonctionnels sont introduits de manière purement syntaxique. La construction des ordinaux limites est gérée par un opérateur unaire, qui permet d'intégrer les suites fondamentales à la notation. Par rapport aux ordinaux de la théorie des ensembles, ce système est à la fois plus souple dans le maniement des opérateurs fonctionnels et plus précis dans l'analyse de la récursion. Établir la terminaison d'un système de réécriture revient alors à résoudre une équation ordinale générée directement à partir des règles du système. Cela s'apparente à la résolution d'une équation récurrente sur les entiers. La preuve de terminaison fournit en outre une mesure gratuite pour la complexité. Plusieurs exemples illustrent cette approche<br>The thesis is about termination in rewriting theory, with particular emphasis on complexity. Termination is an undecidable property of term rewriting systems. However, there exists a combinatorial result that provides a syntactic sufficient condition for termination: Kruskal's tree theorem. This theorem has given rise to several widely used termination orderings in automated reasoning. We study the complexity of those orderings in the case of string and term rewriting systems and give new upper bounds. This work relies on the theory of number-theoretic hierarchies of functions indexed by ordinals. A second part of the thesis is devoted to a modified approach to number-theoretic hierarchies of functions by means of a syntactic approach to ordinal recursion. Our framework of ordinal terms is defined by a set of function symbols whose semantics are given by a rewrite system. Terms are equipped with a binary operator that builds up limit terms from a fundamental sequence. Compared to set-theoretical ordinals, the calculus we obtain is more flexible and involves a more precise analysis of the recursion principle. It appears to be appropriate for finding semantic termination proofs in a systematic way through the reduction to the problem of solving ordinal term inequations. The proof then gives a complexity measure for free. Various examples of applications illustrate this method
5
Viry, Patrick. "La réécriture concurrente." Nancy 1, 1992. http://www.theses.fr/1992NAN10258.
Full textAbstract:
La réécriture concurrente est étudiée pour ses aspects théoriques et sa capacité d'expression, puis un modèle d'implantation sur machine parallèle à mémoire distribuée est propose. Des stratégies concurrentes permettent de caractériser des dérivations aux propriétés intéressantes, le résultat principal étant l'optimalité de stratégie maximale. Une méthode effective est proposée pour combiner les spécifications équationnelles (sans idée de changement, par exemple des types abstraits) et non équationnelles (en général indéterministes et irréversibles, par exemple des transitions d'un système). Elle est ensuite appliquée à l'exemple de CCS, avec en corollaire un cadre unifié pour décrire processus et types abstraits. Le modèle d'implantation proposé est basé sur un algorithme de filtrage de bas en haut. Sa réalisation sur une machine à mémoire distribuée, donc sans état global, est décrite en exprimant les opérations de base par des échanges de messages. La réécriture concurrente semble donc un modèle de programmation intéressant pour de telles machines
6
Slowinski, Karine. "Systèmes de réécriture et langages de mots de figure." Lille 1, 1992. http://www.theses.fr/1992LIL10023.
Full textAbstract:
Une figure 2D constituée de segments unitaires horizontaux et verticaux peut être représentée par une séquence de symboles, chacun d'entre eux engendrant un déplacement unitaire dans l'une des quatre directions: droite, gauche, haut ou bas. L'ensemble de ces symboles est noté P. Ainsi, à tout mot de P* est associée une unique figure inscrite dans le plan cartésien. Nous étudions différents systèmes de réécriture définis sur P* et conservant certaines propriétés des figures associées. D'abord, l'alphabet P contient quatre lettres engendrant des déplacements visibles (crayon baissé). Nous étudions deux systèmes de réécriture S et Sr-red conservant les figures: l'un d'entre eux permet d'obtenir tous les mots décrivant la même figure, l'autre est un système confluent fournissant un unique mot irréductible. Puis, nous complétons cet alphabet avec quatre lettres «blanches» engendrant des déplacements invisibles (crayon levé). Nous définissons un nouveau système de réécriture S' permettant d'obtenir exactement tous les mots décrivant la même figure qu'un mot initial. Pour chacun de ces deux alphabets, nous recherchons un parcours minimal décrivant une figure connexe donnée. Enfin, nous terminons par des résultats de décidabilité relatifs aux langages de mots de figure. Etant donné un langage rationnel inclus dans P*, nous pouvons décider si celui-ci contient des mots de contour de polyominos particuliers. Ces résultats sont établis à l'aide de deux systèmes de réécriture laissant invariantes certaines propriétés des mots de figure
7
Cirstea, Horatiu. "Calcul de réécriture : fondements et applications." Nancy 1, 2000. http://www.theses.fr/2000NAN10037.
Full textAbstract:
L'objet de cette thèse est l'étude d'un calcul permettant de décrire l'application de règles de réécriture conditionnelles et de représenter les résultats obtenus. Nous introduisons le calcul de réécriture, appelé aussi le rho-calcul, qui généralise la réécriture du premier ordre et le lambda-calcul tout en permettant d'exprimer le non-déterminisme. Dans notre approche, l'opérateur d'abstraction ainsi que l'opérateur d'application sont des objets du calcul. Le résultat d'une réduction dans le calcul de réécriture est soit un ensemble vide représentant l'échec de l'application, soit un singleton représentant un résultat déterministe, soit un ensemble ayant plusieurs éléments représentant un choix non-déterministe de résultats. Au cours de cette thèse nous nous concentrons sur les propriétés du calcul de réécriture utilisant un filtrage syntaxique pour lier les variables à leurs valeurs actuelles. Nous définissons des stratégies d'évaluation garantissant la confluence du calcul et nous montrons que ces stratégies deviennent triviales pour des restrictions du calcul de réécriture général à des calculs plus simples comme le lambda-calcul. Le calcul de réécriture n'est pas terminant dans le cas non-typé mais la terminaison forte est obtenue pour le calcul simplement typé. Dans le calcul de réécriture étendu par un opérateur permettant de tester l'échec de l'application nous définissons des termes représentant la normalisation innermost et outermost par rapport à un ensemble de règles de réécriture. En utilisant ces termes, nous obtenons un codage naturel et concis de la réécriture conditionnelle. Enfin, à partir de la représentation des règles de réécriture conditionnelles, nous montrons comment le calcul de réécriture peut être employé pour donner une sémantique au langage ELAN basé sur l'application de règles de réécriture contrôlées par des stratégies<br>This thesis is devoted to the study of a calculus that describes the application of conditional rewriting rules and the obtained results at the same level of representation. We introduce the rewriting calculus, also called the rho-calculus, which generalizes the first order term rewriting and lambda-calculus, and makes possible the representation of the non-determinism. In our approach the abstraction operator as weIl as the application operator are objects of calculus. The result of a reduction in the rewriting calculus is either an empty set representing the application failure, or a singleton representing a deterministic result, or a set having several elements representing a not-deterministic choice of results. In this thesis we concentrate on the properties of the rewriting calculus where a syntactic matching is used in order to bind the variables to their current values. We define evaluation strategies ensuring the confluence of the calcalus and we show that these strategies become trivial for restrictions of the general rewriting calculus to simpler calculi like the lambda-calculus. The rewriting calculus is not terminating in the untyped case but the strong normalization is obtained for the simply typed calculus. In the rewriting calculus extended with an operator allowing to test the application failure we define terms representing innermost and outermost normalizations with respect to a set of rewriting rules. By using these terms, we obtain a natural and concise description of the conditional rewriting. Finally, starting from the representation of the conditional rewriting rules, we show how the rewriting calculus can be used to give a semantics to ELAN, a language based on the application of rewriting rules controlled by strategies
8
Moreau, Pierre-Étienne. "Compilation de règles de réécriture et de stratégies non-déterministes." Nancy 1, 1999. http://www.theses.fr/1999NAN10121.
Full textAbstract:
Les techniques de réécriture ont été développées depuis les années 1970 et appliquées en particulier au prototypage des spécifications formelles algébriques et à la démonstration de propriétés liées à la vérification de programmes. ELAN est un système qui permet de spécifier et d'exécuter des résolveurs de contraintes, des démonstrateurs et plus généralement tout processus décrit par des règles de transformation. Il possède des opérateurs associatifs-commutatifs (AC) et un langage de stratégies qui permettent une gestion fine de l'exploration d'un arbre de recherche et une manipulation aisée d'opérateurs mathématiques tels que les connecteurs booléens, les opérateurs arithmétiques ou les opérateurs de composition parallèle par exemple. Ces deux notions améliorent grandement l'expressivité du langage mais introduisent un double non-déterminisme lié à la possibilité d'appliquer plusieurs règles, de différentes façons, sur un terme donné. Cela rend difficile et généralement peu efficace leur implantation. L'objectif principal de cette thèse est d'étudier des techniques de compilation qui améliorent l'efficacité de ce type de langages. Nous proposons un nouvel algorithme, à base d'automates déterministes, pour compiler efficacement le filtrage syntaxique. Nous définissons ensuite différentes classes de règles pour lesquelles nous proposons un algorithme efficace de filtrage AC. Cet algorithme utilise une structure de données compacte et les automates définis précédemment, ce qui améliore considérablement les performances du processus de normalisation dans son ensemble. [. . . ]
9
Dubois, Hubert. "Système de règles de production et calcul de réécriture." Nancy 1, 2001. http://docnum.univ-lorraine.fr/public/SCD_T_2001_0123_DUBOIS.pdf.
Full textAbstract:
Dans cette thèse nous formalisons des systèmes de règles de production dans le système ELAN basé sur la logique de réécriture où l'application des règles est contrôlée par des stratégies. Le calcul de réécriture fournit une sémantique opérationnelle à ELAN. Nous avons ainsi été amenés à étendre ELAN tout en respectant sa sémantique. Cette extension comporte tout d'abord la possibilité de définir des classes et des objets en ELAN. Ce langage s'implante en ELAN comme un langage objet à prototype. Nous avons également défini un formalisme de règles travaillant à la fois avec une base d'objets et avec une base de contraintes. Ces deux bases coopérent par l'intermédiaire de variables partagées. Ce nouveau paradigme de programmation avec règles, objets, contraintes et stratégies nous permet de modéliser des problèmes de planification ou d'ordonnancement<br>In this thesis, we design production rule systems in the ELAN system which is based on the rewriting logic and where strategies control the application of the rules. The rewriting calculus gives an operational semantics of ELAN. Thus, we developed an extension of ELAN that respects its semantics. Firstly, in this extension, we give the possibility to define classes and objects in ELAN. This language is implemented in ELAN as a prototype object-language. Then, we define a new formalism of rules working together with an object and a constraint store such that objects and constraints share variables. The application of the set of rules is controlled by strategies. This new programming paradigm with rules, objects, constraints and strategies is here used to model problems such that planification or scheduling
10
Guiraud, Yves. "Présentations d'opérades et systèmes de réécriture." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2004. http://tel.archives-ouvertes.fr/tel-00006863.
Full textAbstract:
Cette thèse étudie les propriétés calculatoires des présentations d'opérades, ou systèmes de réécriture de diagrammes de Penrose, et leurs liens avec divers types de systèmes de réécriture classiques. Grâce à des nouveaux critères pour la terminaison et la confluence, on démontre la conjecture sur la convergence de la présentation L(Z2) des Z/2Z-espaces vectoriels, une théorie équationnelle commutative. On montre que les présentations d'opérades sont des généralisations des systèmes de réécriture de mots et des réseaux de Petri et qu'elles fournissent un calcul de gestion explicite des ressources pour les systèmes de réécriture de termes linéaires à gauche. Enfin, on étudie les obstructions à ce même résultat concernant le lambda-calcul. Des annexes présentent les liens entre les opérades et d'autres structures de l'algèbre universelle, ainsi qu'un calcul de substitutions explicites.
11
Santana, de Oliveira Anderson. "Réécriture et modularité pour les politiques de sécurité." Thesis, Nancy 1, 2008. http://www.theses.fr/2008NAN10007/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à la spécification et à l’analyse modulaires de politiques de sécurité flexibles basées sur des règles. Nous introduisons l’utilisation du formalisme de réécriture stratégique dans ce domaine, afin que notre cadre hérite des techniques, des théorèmes, et des outils de la théorie de réécriture. Ceci nous permet d’énoncer facilement et de vérifier des propriétés importantes des politiques de sécurité telles que l’absence des conflits. En outre, nous développons des méthodes basées sur la réécriture de termes pour vérifier des propriétés plus élaborées des politiques. Ces propriétés sont la sûreté dans le contrôle d’accès et la détection des flux d’information dans des politiques obligatoires. Par ailleurs, nous montrons que les stratégies de réécriture sont importantes pour préserver des propriétés des politiques par composition. Les langages de stratégies disponibles dans des systèmes comme Tom, Stratego, Maude, ASF+SDF et Elan, nous permettent de définir plusieurs genres de combinateurs de politiques. Enfin, nous fournissons également une méthodologie pour imposer à des applications existantes, de respecter des politiques basées sur la réécriture via la programmation par aspects. Les politiques sont tissées dans le code existant, ce qui génère des programmes mettant en oeuvre des moniteurs de référence. La réutilisation des politiques et des programmes est améliorée car ils peuvent être maintenus indépendamment<br>In this thesis we address the modular specification and analysis of flexible, rule-based policies. We introduce the use of the strategic rewriting formalism in this domain, such that our framework inherits techniques, theorems, and tools from the rewriting theory. This allows us to easily state and verify important policy properties such as the absence of conflicts, for instance. Moreover, we develop rewrite-based methods to verify elaborate policy properties such as the safety problem in access control and the detection of information flows in mandatory policies. We show that strategies are important to preserve policy properties under composition. The rich strategy languages available in systems like Tom, Stratego, Maude, ASF+SDF and Elan allows us to define several kinds of policy combiners. Finally, in this thesis we provide a systematic methodology to enforce rewrite-based policies on existing applications through aspect-oriented programming. Policies are weaved into the existing code, resulting in programs that implement a reference monitor for the given policy. Reuse is improved since policies and programs can be maintained independently from each other
12
Bousdira, Wadoud. "Etude des propriétés des systèmes de réécriture conditionnelle : mise en oeuvre de deux algorithmes de test de confluence sur les termes clos." Vandoeuvre-les-Nancy, INPL, 1990. http://docnum.univ-lorraine.fr/public/INPL_T_1990_BOUSDIRA_W.pdf.
Full textAbstract:
Définir un type abstrait algébrique par des axiomes conditionnels offre davantage de souplesse et de simplicité que dans un cadre classique, sans précondition. Ceci nous a amené à étudier la théorie conditionnelle de termes dans le but d'obtenir une méthode de décision fondée sur la réécriture de termes. Cependant, cette étude dans le contexte conditionnel soulève des problèmes délicats, principalement liés à la difficulté de formaliser la sémantique sous-jacente à la théorie conditionnelle et de définir des modèles. L'objectif de cette thèse est d'étudier les propriétés des systèmes de réécriture conditionnelle. Notre contribution centrale est la mise en œuvre de deux tests de confluence sur les termes clos. Le premier test est établi pour des systèmes de réécriture hiérarchiques, systèmes construits par strates successives, la précondition d'une règle utilisant exclusivement des opérateurs appartenant aux strates inférieures. Le second test de confluence est établi pour des systèmes décroissants, dont les règles sont définies avec un principe de récurrence structurelle sur leurs composantes. Ces deux classes de systèmes ont été définies et utilisées dans des travaux ultérieurs par divers auteurs pour éviter d'engendrer des dérivations infinies de réécriture. L'originalité du travail est l'utilisation d'un principe de raisonnement par cas, et la possibilité de réécrire une équation conditionnelle aussi bien dans sa partie conséquence que dans sa précondition. Ce processus de simplification s'est révélé souple et puissant et permet de traiter un certain nombre d'applications. Nous abordons également dans notre étude un aspect inhérent à la théorie conditionnelle : le comportement d'une spécification conditionnelle par rapport aux booléens. Ce comportement est fidèle dès lors que les propriétés de consistance et de complétude par rapport à la sorte booléenne sont garanties, assurant de façon intuitive qu'il n'y a ni ajout de booléens, ni confusion entre les deux constantes de vérité true et false. La propriété de complétude d'une spécification conditionnelle est également abordée. Cette propriété étant indécidable même dans la théorie classique, sans préconditions, nous proposons un algorithme fondé sur le raisonnement par cas pour tester si une spécification conditionnelle est complète par rapport à l'ensemble de ses constructeurs. Cet algorithme combine une analyse structurelle par le calcul d'un ensemble de motifs et une analyse par cas par le biais d'un ensemble de conditions utilisées dans la réécriture. Cette condition suffisante de test permet d'appréhender une sous-classe relativement étendue de définitions conditionnelles
13
Ould-Slimane, Hakima. "Réécriture de programmes pour une application effective des politiques de sécurité." Thesis, Université Laval, 2011. http://www.theses.ulaval.ca/2011/28026/28026.pdf.
Full textAbstract:
Durant ces dernières décennies, nous avons assisté à une automatisation massive de la
société selon toutes ses sphères. Malheureusement, cette révolution technologique n’a pas eu
que des bienfaits. En effet, une nouvelle génération de criminels en a profité, afin d’occasionner
davantage d’activités illégales. De ce fait, afin de protéger les systèmes informatiques, il
est devenu plus que primordial de définir rigoureusement des politiques de sécurité ainsi que
de mettre en oeuvre des mécanismes efficaces capables de les appliquer. L’objectif majeur
d’un mécanisme de sécurité consiste souvent à contrôler des logiciels, afin de les contraindre
à “bien” se comporter. Cependant, la plupart des mécanismes de sécurité procèdent par des
méthodes ad hoc qui sont loin d’être efficaces. En outre, ils sont peu fiables, puisqu’il n’y
a aucune preuve sur leur capacité à faire respecter les politiques de sécurité. De là apparaît
la nécessité de concevoir des mécanismes de sécurité alternatifs qui résolvent le problème
de l’application de la sécurité d’une manière formelle, correcte et précise. Dans ce contexte,
notre thèse cible principalement la caractérisation formelle de l’application effective des politiques
de sécurité via des mécanismes basés sur la réécriture de programmes. On entend par
application effective, le fait d’éliminer tous les “mauvais” comportements d’un programme,
tout en conservant tous les “bons” comportements qu’il engendre, et ce, sans compromettre
la sémantique du programme à sécuriser. Nous avons opté pour la réécriture de programmes,
vu sa grande puissance par rapport aux autres mécanismes de sécurité qui sont soit laxistes
soit très restrictifs. Les principaux résultats qui ont été réalisés, afin d’atteindre les objectifs
ciblés par cette thèse sont les suivants :
– Caractérisation formelle de l’application des propriétés de sûreté par la réécriture de
programmes. Il s’agit d’appliquer les propriétés de sûreté qui constituent la classe de
propriétés de sécurité la plus communément appliquée par les mécanismes de sécurité.
– Caractérisation formelle de l’application de n’importe quelle propriété de sécurité par
la réécriture de programmes. Cette contribution montre comment la réécriture de programmes
permet l’application de politiques de sécurité qu’aucune autre classe de mécanismes
de sécurité ne peut appliquer.
– Caractérisation alternative de l’application de la sécurité par une approche algébrique.
Cette contribution propose un formalisme algébrique afin de réduire l’écart
entre la spécification et l’implantation des mécanismes de sécurité basés-réécriture.<br>During the last decades, we have witnessed a massive automation of the society at all
levels. Unfortunately, this technological revolution came with its burden of disadvantages.
Indeed, a new generation of criminals emerged and is benefitting from continuous progress of
information technologies to cause more illegal activities. Thus, to protect computer systems,
it has become very crucial to rigorously define security policies and provide the effective mechanisms
required to enforce them. Usually, the main objective of a security mechanism is to
control the executions of a software and ensure that it will never violate the enforced security
policy. However, the majority of security mechanisms are based on ad hoc methods and thus,
are not effective. In addition, they are unreliable, since there is no evidence on their ability
to enforce security policies. Therefore, there is a need to develop novel security mechanisms
that allow enforcing security policies in a formal, correct, and accurate way. In this context,
our thesis targets the formal characterization of effective security policies enforcement that is
based on programs rewriting. We mean by “effective” enforcement preventing all the “bad”
behaviors of a program while keeping all its "good" behaviors. In addition, effective enforcement
should not compromise the semantics of controlled programs. We have chosen for
rewriting programs, because it has a great power compared to other security mechanisms that
are either permissive or too restrictive. Themain contributions of this thesis are the following :
– Formal characterization of security enforcement of safety properties through program
rewriting. Safety properties represent the main class of properties usually enforced by
security mechanisms.
– Formal characterization of any security property using program rewriting. This contribution
shows how program rewriting allows the enforcement of security policies that
no other class of security mechanisms can enforce.
– Algebraic approach as an alternative formal characterization of program rewriting
based security enforcement. In this contribution, we investigate an algebraic formal
model in order to reduce the gap between the specification and the implementation of
program rewriting based security mechansisms.
14
Fissore, Olivier. "Terminaison de la réécriture sous stratégies." Nancy 1, 2003. http://www.theses.fr/2003NAN10176.
Full textAbstract:
L'objectif de cette thèse est l'étude et la réalisation d'outils pour prouver la terminaison de programmes à base de règles utilisant des stratégies. Partant d'une méthode originale permettant de prouver par induction la terminaison de la réécriture innermost, nous avons amélioré et étendu ce processus de preuve à la stratégie outermost puis aux stratégies locales. Ces processus de preuve ont été implantés dans un outil nommé CARIBOO. Des langages tels qu'ELAN permettent à l'utilisateur de définir ses propres stratégies, par combinaison des règles du programme au moyen d'opérateurs adaptés. Nous avons élaboré une méthode de preuve de terminaison de ces stratégies, basée sur un processus automatique de simplification. Enfin, nous avons adapté notre processus de preuve inductif original à la preuve de la terminaison faible d'un programme, qui fournit à la fois la preuve de l'existence d'une évaluation terminante de toute donnée et un algorithme d'évaluation de cette donnée<br>The aim of this thesis is to study and develop tools for proving termination of rule-based languages using strategies. Starting from an original method for proving, by induction, the termination of innermost rewriting, we enhanced and extended this method to the outermost and local strategies. These proof processes have then been implemented in a tool, named CARIBOO. Such languages as ELAN make it possible for the programmer to define his own strategies, by combining rules of the program with appropriate strategy operators. We came up with a method allowing to prove termination of such strategies, based on an automatic simplification process. Finally, our original inductive proof process has been adapted to show weak termination of programs. This new process provides both the proof of termination of at least one evaluation of any data and an evaluation algorithm for this data
15
Launay, Sylviane. "Complétion de systèmes de réécriture types dont les fonctions sont polymorphes." Paris 7, 1985. http://www.theses.fr/1985PA07F006.
Full text
16
Aimé, Thierry. "Une sémantique par point fixe pour les systèmes de réécriture orthogonaux." Bordeaux 1, 1996. http://www.theses.fr/1996BOR10622.
Full textAbstract:
Les systemes de reecriture comme langage de programmation posent des problemes d'efficacite. Nous proposons une semantique pour les regles de reecriture capable de conduire des optimisations par specialisation. La semantique d'une regle est representee par les classes de comportement qu'elle induit sur ses instances, comportement en terme de sequences de reduction. Alors avec une relation de surreduction contrainte par des problemes d'unification, nous montrons comment exprimer notre semantique sous la forme d'une topdown collecting semantics, permettant a terme une approximation par interpretation abstraite
17
Gnaedig, Isabelle. "Preuves de terminaison des systèmes de réécriture associatifs commutatifs : Une méthode fondée sur la réécriture elle-même." Nancy 1, 1986. http://www.theses.fr/1986NAN10011.
Full textAbstract:
L'objet de cette thèse est la réalisation d'un outil de preuve pour la terminaison des systèmes de réécriture équationnels. Tout particulièrement dans le cas de la théorie associative-commutative. Nous fondant sur un théorème général de terminaison équationnelle, nous construisons un ordre sur les termes, possédant les propriétés requises par ce théorème. Puis nous donnons les justifications théoriques des propriétés de notre ordre, apportant ainsi un outil validé de preuve de terminaison des systèmes de réécriture associatifs-commutatifs. Nous proposons de plus une démonstration complète d'une propriété de l'ordre qui rend cette méthode de preuve implantable dans le cas général des termes avec variables : La stabilité par instanciation. Nous exposons enfin le champ d'application de l'ordre construit, en expliquant son fonctionnement sur une série d'exemples usuels de systèmes de réécriture associatifs-commutatifs
18
Borovanský, Peter. "Le contrôle de la réécriture : étude et implantation d'un formalisme de stratégies." Nancy 1, 1998. http://www.theses.fr/1998NAN10095.
Full textAbstract:
Nous nous intéressons dans cette thèse à la réécriture comme principe d'évaluation et de calcul, et à la logique correspondante. Dans ce cadre, nous étudions différentes possibilités de contrôle des dérivations de réécriture. Nous considérons des règles conditionnelles avec une structure de conditions suffisamment flexible pour exprimer des conditions simples ou structurées, des affectations simples de variables ou le filtrage de motifs. Lorsque les règles de réécriture sont nommées, nous pouvons exprimer le contrôle du système de façon déclarative en spécifiant les séquences de règles et leurs instances qui sont acceptables. Le calcul de preuves de la logique de réécriture, qui représente un modèle théorique de la réécriture, offre la possibilité de généraliser ces séquences de règles aux termes de preuves exprimant quelle instance de la règle est appliquée a quel terme. L’étude d'un langage pour spécifier les ensembles de termes de preuves appelés stratégies est l'apport principal de cette thèse. Les différents aspects, de sémantique, paradigme de programmation et implantation de ce langage dans le système ELAN sont considérés. Les principales caractéristiques du langage de stratégies propose sont : la sémantique basée sur la logique de réécriture, la possibilité d'exprimer les dérivations non-déterministes et concurrentes, le typage strict de toutes les constructions du langage dans le contexte multi-sorte et son extensibilité par de nouvelles constructions. Ce langage de stratégies est défini par un enrichissement d'une théorie de réécriture en une théorie de stratégies qui est également une théorie de réécriture. Cette transformation permet de créer une hiérarchie de stratégies dans laquelle il existe des stratégies qui contrôlent les dérivations d'autres stratégies. Cette thèse illustre plusieurs applications et exemples d'utilisation du langage de stratégies et propose plusieurs méthodes pour son implantation : par un méta-interpréteur optimise en utilisant les techniques d'évaluation partielle ou par la compilation de stratégies.
19
Viêt, Triêm Tông Valérie. "Automates d'arbres et réécriture pour l'étude de problèmes d'accessibilité." Rennes 1, 2003. http://www.theses.fr/2003REN10162.
Full textAbstract:
L'objectif de cette thèse était d'étendre des techniques de réécriture sur les automates d'arbres afin de pouvoir les utiliser pour étudier des propriétés de sécurité sur les protocoles cryptographiques. Notre première partie présente la complétion d'automates d'arbres, procédé qui permet de calculer un automate reconnaissant un sur-ensemble des termes atteignables par un système de réécriture à partir d'un langage initial régulier. Nous proposons une condition dite de linéarité sur les automates permettant d'étendre le calcul aux systèmes de réécriture non linéaires à gauche, une condition sur la fonction d'approximation permettant de rendre le calcul des descendants exact. D'un point de vue algorithmique, nous présentons un algorithme de recherche des instances d'un terme dans un automate qui accelère la complétion. Nous avons implémenté ces résultats dans Timbuk, qui est un logiciel réalisé en Caml et disponible librement à l'URL \it http://www. Irisa. Fr/lande/genet/timbuk/. La deuxième partie de notre travail a été d'utiliser les techniques de complétion décrites précédemment pour vérifier des protocoles cryptographiques. Nous proposons l'exemple de la vérification du protocole View Only de SmartRight développé par Thomson Multimédia et qui vise à protéger des données numériques. La dernière partie de ce travail s'intéresse à la preuve automatique de propriétés initiales. Nous étudions les méthodes de démonstrations automatiques: récurrence explicite, récurrence par réécriture et preuve par cohérence. Nous proposons en premier lieu un algorithme de preuve de propriétés initiales, avant de montrer comment il est possible d'utiliser la complétion d'automates pour automatiser cet algorithme.
20
Fouda, Ndjodo Marcel. "Systèmes de réécriture et cohérence des isomorphismes de types dans les catégories localement closes." Aix-Marseille 2, 1992. http://www.theses.fr/1992AIX22082.
Full textAbstract:
En utilisant une technique de reecriture de termes dans un langage formel de categories, un theoreme de coherence d'une classe d'isomorphismes canoniques est prouvee dans les categories localement closes. Une telle methode trouve ses applications dans l'etude de la decidabilite et de la coherence des isomorphismes de types
21
Boyer, Benoît. "Réécriture d'automates certifiée pour la vérification de modèle." Rennes 1, 2010. http://www.theses.fr/2010REN1S211.
Full textAbstract:
Cette thèse s'intéresse à la vérification de programmes modélisés sous forme de systèmes de règles de réécriture. La vérification de propriétés est basée sur une analyse statique semi-automatique qui construit une sur-approximation, représentée par un automate d'arbres, de l'ensemble des termes atteignables. L'analyse est paramétrée par une abstraction qui doit être suffisamment précise pour que la propriété attendue puisse être vérifiée. Or, il est difficile de construire une telle abstraction à priori. On propose un mécanisme original de raffinement automatique par élagage de l'automate d'arbres lorsque la sur-approximation calculée, trop imprécise, est susceptible de contenir de fausses alarmes. Non seulement l'analyse s'applique à la vérification de propriétés de sûreté par non-atteignabilité, mais on montre qu'elle peut être adaptée afin de vérifier des propriétés temporelles, notamment sur le graphe des appels de méthodes d'un programme Java. Enfin, les outils réalisant cette analyse reposent sur des implémentations optimisées, clairement éloignées de la spécification originale. Pour accroître la confiance en ces outils, on fournit un vérificateur chargé de la validation de leurs résultats à posteriori. La spécification et la correction de ce validateur sont formulées et démontrées dans l'assistant de preuves Coq<br>This thesis addresses the verification of programs, symbolized as term rewriting systems. Program properties are verified using a semiautomatic static analysis that returns a tree automaton recognizing an over-approximation of reachable terms. This analysis is parameterized by an abstraction that has to be precise enough to check the expected property. However, it is generally hard to give such an abstraction to the analysis. Using tree automaton pruning, we propose an original mechanism of automatic refinement, which allows us to avoid false alarms that are contained in the over-approximation. The technique is initially designed to check safety properties by unreachability. We show how to extend it to check temporal properties, especially for properties about the graph of method calls for a Java program. Finally, to increase their performance, the tools performing this analysis are very optimized and their implementation is quite far from of the original specification. To trust the results of these tools, we provide a checker that is in charge of validating the results. The specification and the correction of the checker are designed and proved in the proof assistant Coq
22
Vuotto-Moan, Julie. "Langages d'arbres réguliers et algébriques pour la réécriture et la vérification." Orléans, 2004. http://www.theses.fr/2004ORLE2064.
Full textAbstract:
Partant d'un système de réécriture R basé sur les constructeurs et d'un langage initial E, il est alors possible de calculer l'ensemble des descendants, c’est à dire des termes atteignables à partir de E en appliquant récursivement les règles de R. Calculer l'ensemble des descendants peut être utilisé aussi bien en réécriture (notamment pour vérifier certaines propriétés comme l'accessibilité et la joignabilité) qu'en vérification de protocoles cryptographiques. Les travaux de P. Réty portent sur un calcul d'un ensemble exact de descendants réguliers. Nous les avons étendus en prenant en compte des stratégies de réécriture (innermost, outermost, leftmost et leftmost-innermost). Procéder à un calcul exact nécessitant des restrictions sur R et sur E, nous avons étudié les descendants à travers un langage plus expressif : les langages algébriques d'arbres.
23
Holtzmann, Christelle. "Sous-groupes de petit indice des groupes de tresses et systèmes de réécritures." Dijon, 2008. http://www.theses.fr/2008DIJOS022.
Full textAbstract:
En étudiant, dans la première partie de cette thèse, la classification faite par Artin des homomorphismes transitifs du groupe de tresses Bn dans le groupe symétrique Sk, on observe plusieurs singularités dans les cas n = 4 et n = 6. On applique ensuite à ces résultats des méthodes déjà connues élaborées par Reidemeister et Schreier afin de déterminer, dans une deuxième partie, une présentation à conjugaison près de chacun des sous-groupes de Bn d’indice plus petit ou égal à n. En déterminant les abélianisés de ceux-ci, et grâce à des résultats de cohomologie connus, on en déduira un classement plus fin, qui permet entre autres de cataloguer à isomorphisme près la plupart des sous-groupes de Bn. Après s’être intéressé à des propriétés algébriques provoquées par des actions de groupes, la troisième partie, quant à elle, sera consacrée à l’étude plus précise du problème de la fidélité, qui sera différent selon que l’on s’intéresse aux actions de groupe ou aux actions de monoïdes. Après avoir répondu au problème du mot d’une nouvelle manière grâce à des systèmes de réécriture dans les cas de B3 et B4, on verra comment on peut se servir du type de résultats obtenus pour établir des critères de fidélité en généralisant le lemme du ping-pong et un critère de Krammer<br>Artin’s classification of transitive homomorphisms of the braid group Bn in the symmetric group Sk has several particularities in the cases n = 4 and n = 6. Using these results and a method already developed by Reidemeister and Schreier, we give, in a first time, a presentation up to conjugation of all the subgroups of Bn of smaller index than n. Thanks to known cohomology results, we deduce from their derivate group a beginning of classification up to isomorphisms of the subgroups of Bn of small index. In a second time, we will be interested in fidelity problems. These will be different as we study group actions or monoid actions. Having answered to the "word problem" in the cases of B3 and B4 thanks to a new way using rewriting systems, we use these results in order to generalize the ping-pong lemma and establish some fidelity criteria
24
Johnen, Colette. "Analyse algorithmique des réseaux de Petri : vérification d'espace d'accueil, systèmes de réécriture." Paris 11, 1987. http://www.theses.fr/1987PA112481.
Full textAbstract:
La motivation essentielle de cette thèse est la conception de techniques d'analyse automatique des réseaux de Petri. Elle est articulée autour de deux thèmes : la vérification de la propriété d'espace d'accueil et l'usage des techniques liées aux systèmes de réécriture. Un espace d'accueil est un ensemble de marquages toujours accessible quelle que soit l'évolution du système. Cette propriété permet, par exemple, de vérifier que l'état d'inactivité des processus est toujours accessible. Elle permet aussi de valider des propriétés comportementales (telle la vivacité). Dans la première partie de cette thèse, nous démontrons que la propriété "la réunion finie d'ensembles linéaires ayant mêmes périodes est un espace d'accueil" est décidable. Un algorithme de semi-décision vérifiant un espace d'accueil est présenté dans la deuxième partie. Un traitement par ensemble de marquages permet d'obtenir des résultats particulièrement probants. En une seule étape, on vérifie que l'espace d'accueil est accessible à partir de tous les éléments d'un même ensemble. Pour cela, une classe d'ensembles de marquages facilement caractérisables est définie: les ensembles délimités. Le texte résultant de l'analyse est court, il indique cependant avec précision comment atteindre l'espace d'accueil à partir d'un marquage donné. La troisième partie lie les réseaux de Petri et l'approche des types abstraits algébriques. Une représentation des réseaux de Petri en un ensemble d'équations est établie. Certaines propriétés (caractère borné, confluence) sont reliées directement au système de réécriture obtenu après complétion des équations "à la Knuth-Bendix". D'autres propriétés (quasi vivacité, terminaison finie, accessibilité d'un marquage. . . ) peuvent être prouvées par la convergence du système de réécriture auquel est ajoutée l'équation traduisant la propriété à valider. Des preuves nécessitant d'ordinaire l'élaboration manuelle d'un principe d'induction peuvent être ainsi automatiquement effectuées<br>The main motivation of this thesis is the conception of automatic analysis techniques of Petri nets. The thesis deals with two themes: verification of home space, application of techniques based on rewriting systems. A home space is a always reachable set of markings whatever the evolution of the system may be. This property allows, for instance, verifying that idle state of process is always accessible. It also allows validating behavioural properties (such as liveliness). In the first part, we prove that the property "a finite union of linear sets having the same periods is a home space" is decidable. A semi-decision algorithm checking a home space is presented in the second part. An approach using marking sets leads to especially efficient results. In one stage, it verifies that the home space is reachable from all the markings of a marking set. A class of marking sets which can be easily manipulated is defined (delimited sets). The resulting text is short; nevertheless it precisely indicates how to reach the home space from a given marking. The third part links Petri nets and abstract data types. A representation of Petri nets into a set of equations is established. Some properties (boundless, confluence) are directly related to properties of the rewriting system obtained by completion "à la Knuth-Bendix" of the equations. Some other properties (quasi-liveliness, finite termination, accessibility of a marking. . . ) can be validated by the convergence of the rewriting system obtained by adding the equation corresponding to the property to be proved. Proofs which usually require manual elaborated induction principles can be automatically completed this way
25
Nguyen, Quang Huy. "Calcul de réécriture et automatisation du raisonnement dans les assistants de preuve." Nancy 1, 2002. http://www.theses.fr/2002NAN10144.
Full textAbstract:
Nous étudions dans cette thèse une coopération entre la réécriture du premier ordre et la théorie constructive des types pour automatiser les preuves assistées par l'ordinateur. Nous cherchons par ce travail à mettre en oeuvre la réécriture de manière automatique, sûre et efficace dans l'assistant de preuve Coq à l'aide d'un environnement de programmation externe (ELAN). Deux approches différentes sont étudiées. Dans l'approche mixte, ELAN est utilisé comme un moteur de réécriture externe pour la normalisation des termes dans une tactique réflexive de réécriture en Coq. La trace générée par ELAN de la normalisation est rejouée en Coq pour calculer la forme normale. Afin d'améliorer la performance de la tactique réflexive, nous montrons comment utiliser la réécriture paresseuse pour obtenir une meilleure trace de normalisation. La deuxième approche, appelée externe, est plus flexible car d'une part, elle permet d'obtenir également plusieurs extensions utiles de la réécriture telles que la réécriture conditionnelle ou bien la réécriture modulo l'associativité et la commutativité (AC), et d'autre part, elle peut être facilement adaptée pour d'autres assistants de preuve. Dans cette approche, la réécriture est effectuée entièrement en ELAN et les assistants de preuve ne servent qu'à la vérifier. Nous formalisons donc la notion de terme de preuve des calculs ELAN dans le calcul de réécriture avec substitutions explicites. Nous étudions les propriétés des termes de preuve et les traduisons en syntaxe de l'assistant de preuve pour vérifier les calculs correspondants. Par conséquent, les calculs non-déterministes en ELAN peuvent être certifiés indépendamment, et nous disposons de la réécriture dans l'assistant de preuve. Afin d'améliorer la performance de la vérification des calculs concernant la réécriture modulo AC, nous proposons également une méthode de preuve efficace pour les égalités modulo AC en se basant sur la syntaxicité des théories AC. Ces résultats ont été intégrés dans une nouvelle tactique de réécriture ELAN en Coq<br>In this thesis, we are interested in the cooperation of first-order rewriting and constructive type theory to improve the automation of computer-aided proofs. We aim to integrate (simple, conditional or AC) rewriting in the Coq proof assistant by an automatic, safe and efficient means using an external programming environment ELAN. Two different approaches are investigated. In the mixed approach, ELAN is used as an external rewriting engine for normalising terms in a reflexive rewriting tactic in Coq. The normalisation trace generated by ELAN is replayed in Coq to compute the corresponding normal form. In order to improve the performance of this reflexive tactic, we show how to use lazy rewriting for producing compact normalisation traces. The second approach called external is more flexible since it also covers several useful extensions of term rewriting such as conditional rewriting and AC rewriting, and it can be easily adapted to other proof assistants. In this approach, term rewriting is entirely performed in ELAN and proof assistants are only used for checking purpose. We formalise the notion of proof term for ELAN computations in the rewriting calculus with explicit substitutions. We investigate the equivalent properties of the proof terms and translate them into the syntax of proof assistant in order to check the corresponding computations. By this work, non-deterministic ELAN computations can be independently certified and we obtain term rewriting in proof assistant. In order to speed up proof-checking of the computations involving AC rewriting, we also propose an efficient method for proving equalities modulo AC based on the syntacticness of AC theories. These results have been integrated in a new ELAN-based rewriting tactic in Coq
26
Deruyver, Aline. "Deux aspects de la réécriture : un laboratoire pour les automates VALERIAN : un système de sémonstration automatique des théorèmes." Lille 1, 1991. http://www.theses.fr/1991LIL10008.
Full textAbstract:
Dans ce mémoire nous étudions deux aspects de la réécriture. Le premier travail est une contribution à l'étude structurelle de certaines classes de réécriture. Nous montrons comment certains problèmes d'accessibilité se traitent à la lumière des automates finis d'arbres. De plus nous avons construit un logiciel nommé Valerian résolvant certains de ces problèmes en temps réel. Le second travail consiste en la mise en oeuvre d'un système de démonstration automatique de théorème basé sur un calcul par superposition et fonctionnant pour des clauses logiques du premier ordre avec équations
27
Lippi, Sylvain. "Théorie et pratique des réseaux d'interaction." Aix-Marseille 2, 2001. http://www.theses.fr/2002AIX22012.
Full text
28
Langar, Mohamed Mahjoub. "Cadre algébrique pour le renforcement de politique de sécurité sur des systèmes concurrents par réécriture automatique de programmes." Thesis, Université Laval, 2010. http://www.theses.ulaval.ca/2010/27655/27655.pdf.
Full textAbstract:
La société moderne est de plus en plus dépendante de l'informatique dont le rôle est devenu tellement vital au point que tout dysfonctionnement peut engendrer des pertes considérables voire des conséquences irréversibles telles que la perte de vies humaines.
Pour minimiser les dégâts, plusieurs techniques et outils ont été mis en place au cours des dernières années. Leur objectif est de faire en sorte que nos systèmes informatiques fonctionnent <<~tout le temps~>>, et ce, tout en produisant les résultats escomptés. La duplication du matériel et les tests de logiciels sont parmi les techniques les plus utilisées. Cependant, sans méthodes formelles, rien n'est garanti et des problèmes peuvent surgir à tout moment.
En contrepartie, l'utilisation de méthodes formelles n'est pas à la portée de tout le monde y compris les programmeurs chevronnés et la tâche reste subtile et complexe même pour les spécialistes. Quelques lignes de code nécessitent parfois des centaines de lignes de preuve difficiles à lire et à comprendre. Malgré tout, leur utilisation n'est plus un luxe, mais plutôt nécessaire afin d'éviter les dégâts engendrés par les mauvais fonctionnements de nos systèmes critiques.
Le principal objectif de notre recherche est de développer un cadre formel et automatique pour le renforcement de politique de sécurité sur des systèmes concurrents. Plus précisément, l'idée consiste à ajouter dans un programme des tests à des endroits soigneusement calculés pour qu'une politique de sécurité soit respectée. La nouvelle version du programme préserve toutes les traces de la version originale respectant la politique de sécurité et bloque les traces qui ne peuvent plus respecter la politique de sécurité même si elles sont complétées par certains suffixes. Les principaux résultats ayant contribué à l'atteinte de cet objectif sont :
1. La définition d'une algèbre de processus [symbol] offrant un cadre purement algébrique pour le renforcement de politique de sécurité sur des systèmes concurrents. Plus précisément, nous avons défini un nouvel opérateur qui permet de renforcer, d'une manière intuitive, une politique de sécurité sur un système concurrent.
2. La définition d'une logique, dénotée par [symbol], inspirée des expressions régulières étendues. En effet, [symbol] est une logique linéaire qui exprime la classe de langage régulier, mais avec la possibilité d'exprimer des propriétés infinies.
3. La définition d'une algèbre [symbol] basée sur l'algèbre [symbol]. [symbol] définit un nouvel opérateur de renforcement qui tient compte de l'introduction de la logique.
4. Le développement d'une technique d'optimisation qui, pour une certaine classe de propriétés de sécurité, permet de réduire le nombre de tests insérés dans le programme renforcé.<br>One of the important goals of the software development process is proving that the produced systems always meet their requirements. However, establishing this goal is not only subtle and complex, but also requires high qualified persons. In addition, this operation is mostly omitted due to its high cost and the system is tested while trying to reduce the risk of errors as much as possible. The cost is, nevertheless, paid when this operation is required in order to avoid catastrophic consequences and major errors. In these cases, tools like theorem prover and those used for automatic generation of software are helpful to significantly reduce the cost of proof. Our aim is that this tool proves to be powerful and simple enough to generate benefits even to small companies and individuals with scarce budgets and limited theoretical skills .
Many promising formal frameworks for automatic enforcement of security policies in programs have been proposed during the last years. Their goal is to ensure that a program respects a given security policy which generally specifies acceptable executions of the program and can be expressed in terms of access control problems, information flow, availability of resources, confidentiality, etc. The literature records various techniques for enforcing security policies belonging to mainly two principal classes: static approaches including typing theory, Proof Carrying Code, and dynamic approaches including reference monitors, Java stack inspection. Static analysis aims at enforcing properties before program execution. In dynamic analysis, however, the enforcement takes place at runtime by intercepting critical events during the program execution and halting the latter whenever an action is attempting to violate the property being enforced. Recently, several researchers have explored rewriting techniques in order to gather advantages of both static and dynamic methods. The idea consists in modifying a program statically, so that the produced version respects the requested requirements. The rewritten program is generated from the original one by adding, when necessary, some tests at some critical points to obtain the desired behaviors.
This thesis aims to propose an algebraic and automatic approach that could generate from a given program, and a security policy, a new version of this program that respects the requested security policy. More precisely, we define an operator [symbol] that takes as input a process [symbol] and a security policy [symbol] and generates [symbol], a new process that respects the following conditions:
[symbol] "satisfies" the security policy [symbol].
[symbol], behaviours of [symbol] are also behaviours of [symbol].
[symbol], all good behaviours of [symbol] are also behaviours [symbol].
The main results of our research are the following~:
1. The definition of a process algebra [symbol] offering an algebraic framework for the enforcement of security policies on concurrent systems.
2. The definition of a logic, denoted by [symbol], inspired from Kleene algebras and regular expressions. Basically, it allows to specify properties that can be checked on a trace-based model and properties related to infinite behavior (e.g. a server should not send the password of users). The choice of this logic is motivated by its syntax that is close to the one chosen for processes. In fact, this similarity is helpful to simplify the definition of our formal monitor.
3. The development of an optimization technique which, for a certain class of security properties, reduces the number of tests added in the target.
29
Alouini, Elyès. "Etude et mise en oeuvre de la réécriture conditionnelle concurrente sur des machines parallèles à mémoire distribuée." Nancy 1, 1997. http://www.theses.fr/1997NAN10011.
Full textAbstract:
La réécriture de termes est un concept maintenant bien connu, qu'on retrouve à la base de langages de programmation de haut niveau tel qu'OBJ, ou encore comme mécanisme fondamental pour le calcul formel et la démonstration automatique. Cette thèse est consacrée à la définition et l'implantation d'un modèle de réécriture conditionnelle concurrent sur des machines parallèles à mémoire distribuée. Notre approche est de profiter du parallélisme de données que l'on rencontre dans les structures de termes. La réécriture concurrente consiste à appliquer simultanément plusieurs règles sur un même terme. Dans un premier temps, nous décrivons la formalisation de notre modèle de calcul dans le cadre de la logique de réécriture de J. Meseguer. Dans le but d'étendre ce modèle aux règles conditionnelles, nous définissons ensuite une transformation d'un système de réécriture conditionnelle en un système de réécriture non conditionnelle. Nous détaillons notre choix d'implantation du modèle de calcul et nous décrivons le passage du modèle abstrait de la réécriture concurrente conditionnelle à un modèle réel implantable sur des machines parallèles à mémoire distribuée. Le modèle d'implantation est basé sur la réécriture de termes représentés par des graphes particuliers appelés "jungles". Un mécanisme fondé sur des échanges asynchrones de messages permet de réaliser l'opération de réécriture. Nous proposons un algorithme de glanage concurrent opérant sur les noeuds du graphe à réduire. Le logiciel ReCo met en oeuvre directement le modèle opérationnel de la réécriture conditionnelle concurrente en utilisant le standard MPI ou la bibliothèque PVM pour le passage des messages entre processus. Pour valider et expérimenter notre modèle de calcul concurrent, différents benchmarks de calculs parallèles de formes normales de termes sont réalisés<br>Term Rewriting is a well-known concept used in many programming languages such OBJ, as well as a fundamental mechnaism for automated deduction and formal computation. This thesis is an approach to the definition and the implementation of a conditional concurrent model on distributed memory machines. Our approach is to use the data parallelism present in term structure. Concurrent rewriting consists in the simultaneous application of several rewriting rules on the same term. First, we describe the formalisation of our model in the context of J. Meseguer's rewriting logic. To extend the model to conditional rewriting, we define a transformation from conditional to unconditional rewriting systems. We detail the implementation model and we describe the transition from the conditional concurrent rewriting abstract model to an operational model which can be implemented on distributed memory machines. The implemented model is based on asynchronous exchange of messages. We propose a concurrent garbage algorithm reclaiming unused nodes of the graph. The ReCo system implements the oerational model using MPI ou PVM message passing interface library. To validate and to experiment our implementation, different benchmarks for computing term normal forms are realised
30
Selhab, Sohame. "Logiques et réécriture." Nancy 1, 1998. http://www.theses.fr/1998NAN10207.
Full textAbstract:
La première partie de notre thèse est dédiée à l'étude de l'élimination de coupures dans le calcul de séquents classique en s'appuyant sur le théorème de Gentzen (1934). Ce dernier stipule que toute preuve en calcul de séquents classique peut être transformée en une preuve normale ne faisant pas intervenir la règle de coupure. Gentzen a démontré ce résultat en décrivant une procédure de normalisation. Mais sa démonstration ainsi que celles de Tait et de Girard prouvent la terminaison de cette procédure seulement pour une stratégie particulière. La question que nous nous sommes posée est : comment montrer que la procédure d'élimination de coupures termine quelque soit la stratégie employée (une forme forte du théorème de Gentzen) ? L’approche que nous avons alors adoptée consiste à utiliser des techniques standards de réécriture. Plus précisément, nous représentons les preuves par des termes puis nous construisons un système de réécriture réalisant l'élimination de coupures. La définition de ces règles de réécriture fait abstraction de toute stratégie. La preuve de terminaison du système de réécriture construit établit alors une forme forte d'élimination de coupures pour le calcul de séquents considéré. Cette nouvelle approche produit une démonstration générique. En effet nous avons appliqué avec succès cette méthode aux calculs de séquents classique (LK), intuitionniste (LJ1) et linéaires (MALL1 et CLL). En plus de la palette de techniques de preuve de terminaison purement syntaxiques, nous avons employé des méthodes sémantiques pour la preuve de terminaison de la procédure d'élimination de coupures dans le cas des calculs MALL1 et CLL. L’avantage de cette seconde méthode est l'extraction aisée de bornes sur la longueur des séquences de réécriture. En fin de cette thèse, nous nous sommes intéressés aux travaux récents de de Groote et Kfoury & Wells qui s'apparentent à notre travail. En effet ils utilisent des méthodes à caractère syntaxique pour établir la forte normalisation de divers lambda-calculs typés. En combinant un cas particulier de la preuve de de Groote et une version modifiée de la preuve de Kfoury et Wells, nous obtenons une preuve alternative de la forte normalisation du lambda-calcul simplement typé. Cette dernière syntaxique et plus constructive utilise en partie des techniques relevant de la théorie de la réécriture.
31
Domenjoud, Éric. "Outils pour la déduction automatique dans les théories associative-commutatives." Nancy 1, 1991. http://www.theses.fr/1991NAN10179.
Full textAbstract:
Le but de cette thèse est de proposer de nouveaux outils pour la déduction automatique dans les théories associative-commutatives. Dans le cadre de la réécriture, nous proposons une nouvelle définition de la réécriture modulo ac en restreignant la réécriture de Peterson et Stickel à certaines positions appelées positions utiles modulo ac. Ceci permet de réduire d'une part le nombre de paires critiques à calculer lors de la complétion d'un système de réécriture. Dans le domaine de l'unification, nous proposons tout d'abord un nouvel algorithme de résolution des systèmes d'équations diophantiennes linéaires qui interviennent dans l'unification modulo ac, ainsi qu'une formule permettant un dénombrement rapide des solutions minimales d'un problème d'unification modulo ac. Cela permet de développer des stratégies pour tous les processus dans lesquels on est amène à faire un choix sur le problème à résoudre, comme par exemple le calcul de paires critiques lors de la complétion d'un système de réécriture, ou encore la résolution paresseuse de contraintes en logique équationnelle contrainte. Enfin, nous proposons une méthode permettant, pour toute spécification dont la présentation contient les axiomes d'associativité et de commutativité, d'en construire une extension conservative modulo laquelle l'unification devient moins complexe en termes de nombre de solutions minimales. Les solutions d'un problème d'unification modulo la nouvelle spécification peuvent alors vues comme des schémas représentent chacun un grand nombre des solutions modulo la spécification de départ
32
Oliveira, Kiermes Tavares Claudia Fernanda. "Un système de types pour la programmation par réécriture embarquée." Electronic Thesis or Diss., Université de Lorraine, 2012. http://www.theses.fr/2012LORR0015.
Full textAbstract:
Dans le domaine de l'ingénierie du logiciel, les systèmes de types sont souvent considérés pour la prévention de l'occurrence de termes dénués de sens par rapport à une spécification des types. Dans le cadre de l'extension d'un langage de programmation avec des caractéristiques dédiées, le typage de ces dernières doit être compatible avec les caractéristiques du langage hôte. Cette thèse se situe dans le contexte de la réécriture de termes embarquée dans la programmation orientée objet. Elle vise à développer un système de types avec sous-typage pour le support du filtrage de motifs associatif sur des termes algébriques construits sur des opérateurs variadiques. Ce travail s'appuie sur le langage de réécriture Tom qui fournit des constructions de filtrage de motifs et des stratégies de réécriture à des langages généralistes comme Java. Nous décrivons l'évaluation de code Tom à travers la définition de la sémantique opérationnelle de ce langage en tant qu'élément essentiel de la preuve de la sûreté du système de types. Celui-ci inclut la vérification de types ainsi que l'inférence de types à base de contraintes. Le langage de contraintes est composé d'une part, de contraintes d'égalité, résolues par unification, d'autre part, de contraintes de sous-typage, résolues par la combinaison de phases de simplification, de génération d'une solution et de ramassage de miettes. Le système de types a été intégré au langage Tom, ce qui permet une plus forte expressivité et plus de sûreté a fin d'assurer que les transformations décrites par des règles de réécriture préservent le type des termes<br>In software engineering, type systems are often considered in order to prevent the occurrence of meaningless terms in regard to a type specification. When extending a given programming language with new dedicated features, the typing of these features must be compatible with the ones in the host language. This thesis is situated in the context of term rewriting embedded in object-oriented programming and aims to develop a safe type system featuring subtyping for the support of associative pattern matching on algebraic terms built from variadic operators. In this work we consider the Tom rewriting language that provides associative pattern matching constructs and rewrite strategies for Java. We describe Tom code evaluation through the definition of the operational semantics of the Tom language as an essential element to show that the type system is safe. The type system includes type checking and constraint-based type inference. The constraint language is composed of equality constraints solved by unification and subtyping constraints solved by a combination of simplification, generation of solution and garbage collecting. The type system was integrated in Tom which provides both stronger expressiveness and more safety able to ensure that the transformations described by rewrite rules preserve the type of terms
33
Eichler, Cédric. "Modélisation formelle de systèmes dynamiques autonomes : graphe, réécriture et grammaire." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30057/document.
Full textAbstract:
Les systèmes distribués modernes à large-échelle évoluent dans des contextes variables soumis à de nombreux aléas auxquels ils doivent s'adapter dynamiquement. Dans ce cadre, l'informatique autonome se propose de réduire les interventions humaines lentes et coûteuses, en leur préférant l'auto-gestion. Elle repose avant tout sur une description adéquate de ses composants, de leurs interactions et des différents aspects ou topologies qu'il peut adopter. Diverses approches de modélisation ont étés proposées dans la littérature, se concentrant en général sur certains du système dynamique et ne permettent ainsi pas de répondre à chacune des problématiques inhérentes à l'auto-gestion. Cette thèse traite de la modélisation basée graphes des systèmes dynamiques et de son adéquation pour la mise en œuvre des quatre propriétés fondamentales de l'informatique. Elle propose quatre principales contributions théoriques et appliquées. La première est une méthodologie pour la construction et la caractérisation générative de transformations correctes par construction dont l'application préserve nécessairement la correction du système. La seconde contribution consiste en une extension des systèmes de réécriture de graphe permettant de représenter, mettre à jour, évaluer et paramétrer les caractéristiques d'un système aisément et efficacement. Une étude expérimentale extensive révèle un net gain d'efficacité vis à vis de méthodes classiques. Les deux dernières contributions s'articulent autour de l'élaboration de deux modules de gestions visant : (1) des requêtes de traitement d'événements complexes et (2) tout système Machine-à-Machine se conformant au standard ETSI M2M<br>Modern, large-scale systems are deployed in changing environments. They must dynamically adapt to context changes. In this scope, autonomic computing aims at reducing slow and costly human interventions, by building self-managed systems. Self-adaptability of a system is primarily based on a suitable description of its components, their interactions and the various states it can adopt. Various modeling approaches have been elaborated. They usually focus on some aspects or properties of dynamic systems and do not tackle each of self-management's requirements. This manuscript deals with graph-based representations of dynamic systems and their suitability for the implementation of autonomic computing's four fundamental properties : self-optimization, self-protection, self-healing and self-configuring. This thesis offers four principal theoretical and applied contributions. The first one is a methodology for the construction and generative characterization of transformations correct by construction whose application necessarily preserves a system's correctness. The second one consists in an extension of graph rewriting systems allowing to easily and efficiently represent, update, evaluate and configure a system's characteristics. An experimental study reveals a significant efficiency gain with regard to classical methods. The two lasts contribution are articulated around the design of two autonomic managers driving: (1) complex events processing requests and (2) any Machine-to-Machine system complying to the ETSI M2M2 standard
34
Reilles, Antoine. "Réécriture et compilation de confiance." Electronic Thesis or Diss., Vandoeuvre-les-Nancy, INPL, 2006. http://www.theses.fr/2006INPL084N.
Full textAbstract:
La plupart des processus informatiques mettent en jeu la notion de transformation, en particulier la compilation. Nous nous intéressons dans cette thèse à fournir des outils et des méthodes, utilisant la réécriture, permettant d'accroître la confiance que l'on peut placer dans ces processus. Nous développons dans un premier temps un cadre permettant de valider la compilation de constructions de filtrage, produisant une preuve formelle de la validité de la compilation, ainsi qu'un témoin de cette preuve, à chaque exécution du compilateur. Afin de permettre l'écriture sûre de transformations complexes, nous proposons un générateur de structures de données efficaces intégrant des invariants algébriques, et un langage de stratégies permettant de contrôler l'application des transformations. Ces résultats constituent donc une avancée vers la constitution de methodes génériques sûres pour le développement de transformations de confiance<br>Most computer processes involve the notion of transformation, in particular the compilation processes. We interest in this thesis in providing tools and methods, based on rewriting, giving the opportunity to increase the confidence we can place into those processes. We develop first a framework used to validate the compilation of matching constructs, building a formal proof of the validity of the compilation process along with a witness of this proof, for each run of the compiler. Then, in order to allow one to write safely complex transformations, we propose a tool that generates an efficient data structure integrating algebraic invariants, as well as a strategy language that enables to control the application of transformations. Those results can be seen as a first step towards the constitution of generic and safe methods for the development of trustworthy transformations
35
Majoul, Salam. "Etude et mise en oeuvre d'un modèle de coordination basé sur la réécriture." Toulouse 3, 2000. http://www.theses.fr/2000TOU30171.
Full text
36
Ben, Cherifa Ahlem. "Preuves de terminaison des systèmes de réecriture : un outil fondé sur les interprétations polynomiales." Nancy 1, 1986. http://www.theses.fr/1986NAN10175.
Full textAbstract:
L'objectif de cette thèse est une étude de la terminaison des systèmes de réécriture de termes en utilisant des interprétations polynomiales. Nous caractérisons aussi les interprétations polynomiales des opérateurs associatifs cumutatifs (ou AC), fournissant ainsi un nouvel ordre, utilisant le même processus que celui adopté pour la terminaison de la réécriture standard. De plus nous avons veillé à utiliser le principe de la terminaison associative-commutative, pour l'étendre à d'autres catégories de réécriture équationnelle. Enfin nous étendons notre approche aux produits cartésiens sur les polynômes, permettant ainsi l'utilisation de plus d'une interprétation pour un symbole de fonction donné. Nous utilisons alors, pour la preuve de la terminaison, les interprétations polynomiales classiques ou les interprétations polynomiales associatives-commutatives et un ordre lexicographique. Un autre problème a été abordé dans sa généralité au cours de ce travail: il s'agit de la détermination des bonnes interprétations polynomiales. En nous fondant sur notre expérience, nous avons pu fournir à l'utilisateur quelques bonnes suggestions afin de l'aider dans le choix de ses interprétations.
37
Kervarc, Romain. "Systèmes de types purs et substitutions explicites." Lyon, École normale supérieure (sciences), 2007. http://www.theses.fr/2007ENSL0399.
Full textAbstract:
La théorie des types est actuellement considérée comme un outil fondamental en informatique, car elle établit un lien entre un calcul d'une part et un système logique d'autre part, ce qui permet d'exprimer des propriétés variées. Les systèmes de types purs sont un formalisme général dans lequel on peut définir un grand nombre de systèmes logiques. Cette thèse présente l'extension de ces systèmes dans deux cadres : un calcul à substitutions explicites et un calcul de séquents classique, et étudie les propriétés des systèmes obtenus, en particulier la correction des types, la reconstruction de dérivations, la réduction du sujet et la normalisation forte. Dans le premier cas, on introduit une nouvelle règle d'inférence de type inspirée de la synthèse de type et une nouvelle technique de démonstration avec un ordre sur les dérivations. Dans le second cas, on étudie en particulier la notion de bonne formation et l'on s'intéresse à des réorganisations perpétuelles de chemin de réduction<br>Type theory is currently considered as a fundamental tool in computer science, since it establishes a link between a calculus on the one hand and a logical system on the other hand, which allows to state various properties. Pure type systems are a very general formalism in terms of which many logical systems may be expressed. This thesis presents the extension of those systems in two frameworks: a calculus with explicit substitutions and a classical sequent calculus, and studies the properties of the obtained systems, especially type correction, derivation reconstruction, subject reduction, and strong normalisation. In the first case, a new typing rule is introduced, inspired by type inference considerations, and also a new proof method, relying on an order upon derivations. In the second case, the notion of well-formedness is more particularly studied, and one also considers perpetual reorganisations of reduction paths
38
Maazouzi, Zahir. "Conception des circuits programmables par la réécriture conditionnelle et étude des aspects vectoriels des fonctions booléennes." Orléans, 2001. http://www.theses.fr/2001ORLE2042.
Full textAbstract:
Dans ce travail, nous proposons une méthode de conception originale pour les circuits combinatoires de type FPLA, basée sur des techniques de réécriture conditionnelle. Ce cadre théorique fort nous permet d'obtenir une méthode correcte (les solutions proposées sont exactes) et complète. L'implémentation du système de règles d'inférences, s'est faite dans un premier temps en utilisant un démonstrateur automatique dans les théories de Horn. Pour améliorer les performances nous avons développé des heuristiques et des stratégies, propres à nos objectifs. Puis nous avons élaboré un nouveau logiciel en adaptant les structures de données et ne conservant que les traitements nécessaires à notre problématique. Nous avons ensuite étudié l'aspect vectoriel de l'algèbre de Boole et ainsi dégagé de nouvelles propriétés sur les tables de vérités et la notion de ±somme de produitsα d'une fonction booléenne. Ceci nous a permis d'optimiser considérablement en mémoire et en temps notre méthode, tout en conservant la correction et la complétude. L'efficacité restant toutefois limitée, nous avons repris les propriétés dégagées et proposé une nouvelle représentation dite ±chapeauα des produits booléennes. Cette nouvelle représentation a l'avantage de la représentation dite syntaxique tout en conservant les propriétés établies sur la forme vectorielle. Ceci nous a permis de dépasser le cadre de conception de circuit et de proposer un arbre ternaire ayant pour racine une fonction booléenne et codant sous forme ±chapeauα l'ensemble de ses implicants premiers. Cet arbre inclut la nouvelle notion de sémantique d'une fonction booléenne qui optimise notre méthode. Cette approche a aussi été utilisée pour le calcul d'une couverture irredondante d'une fonction. La complexité théorique et la comparaison avec d'autres méthodes existantes sont étudiées et l'amélioration est confirmée en pratique par le développement d'un prototype ayant comme structures de données sous-jacente les BDD.
39
Wack, Benjamin. "Typage et déduction dans le calcul de réécriture." Phd thesis, Université Henri Poincaré - Nancy I, 2005. http://tel.archives-ouvertes.fr/tel-00010546.
Full textAbstract:
Le calcul de réécriture est un lambda-calcul avec filtrage. Cette thèse est consacrée à l'étude de systèmes de types pour ce calcul et à son utilisation dans le domaine de la déduction.<br /><br />Nous étudions deux paradigmes de typage. Le premier est inspiré du lambda-calcul simplement typé, mais un terme peut y être typé sans être terminant. Nous l'utilisons donc pour représenter des programmes et des systèmes de réécriture. La seconde famille de systèmes de types que nous étudions est adaptée des Pure Type Systems. Nous en démontrons la normalisation forte grâce à une traduction vers le lambda-calcul typé.<br /><br />Enfin nous proposons deux approches pour l'utilisation du calcul de réécriture en logique. La première consiste à définir des termes de preuve pour la déduction modulo à l'aide des systèmes fortement normalisants. Dans la seconde, nous définissons une généralisation de la déduction naturelle et nous montrons que le filtrage est utile pour représenter les règles de ce système de déduction.
40
Malbos, Philippe. "Critères de finitude homologique pour la non convergence des systèmes de réécriture de termes." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2004. http://tel.archives-ouvertes.fr/tel-00008784.
Full textAbstract:
L'algorithme de complétion de Knuth-Bendix permet, dans certains<br />cas, d'utiliser les systèmes de réécriture pour décider le<br />problème du mot dans un monoïde. Le problème du mot est alors<br />réduit a un calcul de forme normale. Cependant, tous les monoïdes<br />décidables ne peuvent pas être résolus de cette façon. Un<br />programme, initie par Squier, vise a caractériser par des<br />invariants algébriques la classe des monoïde décidables par<br />réécriture.<br />L'objectif de cette thèse est d'étendre ce travail a la réécriture<br />de termes.<br />Nous établissons des conditions de finitude homologique pour<br />l'existence de présentations convergentes de type fini par<br />réécriture de termes de théories équationnelles du premier ordre<br />avec une sorte. Une théorie équationnelle est sémantiquement<br />décrite par une théorie algébrique au sens de Lawvere. Nous<br />introduisons l'homologie de ces théories à coefficients dans les<br />bimodules non additifs, comme généralisation de l'homologie de<br />MacLane des anneaux. Cette homologie admet une interprétation en<br />terme d'homologie de Hochschild-Mitchell de la petite catégorie<br />sous-jacente. Nous généralisons les résolutions libres de Squier<br />et Kobayashi, établies en réécriture de mots, à la réécriture de<br />petites catégories. En utilisant ces résolutions, nous montrons<br />qu'une théorie algébrique admettant une présentation convergente<br />de type fini est de type bi-$\mathrm(PF)_(\infty)$. Nous<br />construisons une théorie équationnelle, non unaire, décidable et<br />n'admettant pas de présentation convergente de type fini.
41
Monate, Benjamin. "Propriétés uniformes de familles de systèmes de réécriture de mots paramétrées par des entiers." Paris 11, 2002. http://www.theses.fr/2002PA112026.
Full textAbstract:
Dans cette thèse nous proposons un formalisme étendant la notion de réécriture contrainte sur les mots : la réécriture paramétrée. Cette dernière permet de décrire de façon uniforme des familles, éventuellement infinies, de systèmes de réécriture de mots qui dépendent de paramètres entiers. Ce formalisme permet l'étude des propriétés uniformes des familles de structures algébriques présentées par de tels systèmes. Par exemple, nous traitons le cas de la famille composée des groupes de permutations d'ordre N, où N est un paramètre prenant ses valeurs dans les entiers naturels. Nous donnons des algorithmes permettant de faire des preuves équationelles qui sont correctes, dites preuves uniformes, pour toutes les valeurs des paramètres. Ensuite nous étudions les preuves par réécriture et montrons un lemme des paires critiques analogue à celui présent en réécriture standard. Nous en déduisons un algorithme de complétion pour les systèmes de réécriture paramétrés. Enfin nous proposons un algorithme permettant le calcul du cardinal de l'ensemble des formes normales des algèbres paramétrées. Au fil du manuscrit, nous présentons une syntaxe pour la réécriture paramétrée qui est très proche de celle utilisée en mathématique pour présenter équationellement des structures dénombrablement engendrées. Nous indiçons les lettres par des expression arithmétiques, puis nous définissons les notions de mots avec exposants entiers et les mots contenant des produits finis. Par l'étude de nombreux exemples issus de la littérature mathématique, nous montrons que notre formalisme permet de représenter et d'étudier automatiquement des familles de structures qui auparavant nécessitaient de longs raisonnements mathématiques fastidieux<br>In this thesis, we introduce a formalism extending the string contrained rewriting : the parameterized string rewriting. It enables one to describe uniformly infinite families of string rewriting systems which depend on integers parameters. With this formalism, one can study uniform properties of algebraic structures families presented by such systems. For example, we study the family composed of the groups of permutations of order N, where N is a parameter with values in the non negative integers. We give algorithms to build equational proofs that are correct for each value of the parameters. Thereafter we study rewriting proofs and prove a critical pair lemma for parameterized rewriting, which is very similar to the one in classical rewriting. We give a completion algorithm for parameterized rewriting. Finally we propose an algorithm which computes the cardinal of the set of normal forms in parameterized algebras. The syntax that we introduce in the document is very close to the syntax used in mathematics to give equational presentations of denumerable generated structures. We use letters indexed by arithmetic expressions, words with integers exponents and finite products. Through several examples, coming from mathematical literature, we show our formalism in action, studying automatically infinite families of structures which would be studied with long and tedious mathematical proofs
42
Ringeissen, Christophe. "Combinaison de résolutions de contraintes." Nancy 1, 1993. http://docnum.univ-lorraine.fr/public/SCD_T_1993_0369_RINGEISSEN.pdf.
Full textAbstract:
L'objet de cette thèse est l'étude de la combinaison des résolutions de contraintes. La notion de contrainte a permis d'accroitre sensiblement l'efficacité des systèmes de déduction à la base de la programmation en logique et de la démonstration automatique. A l'heure actuelle, les systèmes de déduction incorporent le plus souvent un seul domaine de calcul qui peut être suivant les cas, les termes du premier ordre, les entiers, les booléens, les domaines finis ou algèbres finies. Le problème de combinaison consiste à étendre l'utilisation de ces algorithmes afin qu'ils puissent résoudre des contraintes mixtes sur la réunion des domaines de calcul. Un cas particulièrement important est celui de la combinaison d'algorithmes d'unification, ou les contraintes sont des équations et les domaines, des théories équationnelles à signatures disjointes. Dans cette thèse, nous généralisons l'emploi de techniques de combinaison aux résolutions de contraintes. Nous présentons des algorithmes d'unification dans des théories équationnelles décomposables en sous-théories non nécessairement disjointes pour lesquelles des principes de combinaison sont toujours applicables. Dans la classe optimale des théories partiellement linéaires que nous introduisons, la résolution d'un problème combiné spécifique comme le filtrage s'effectue par résolution de sous-problèmes tout aussi spécifiques. L'approche suivie permet d'appliquer la plupart de nos algorithmes de combinaison de l'unification, du filtrage ou du problème du mot au problème de satisfaisabilite qui revêt une importance grandissante en programmation logique et en déduction automatique avec contraintes. Nous proposons un cadre formel pour la combinaison de résolveurs de contraintes symboliques. Le langage de contraintes combiné et le résolveur qui en résultent sont illustrés par la combinaison de résolveurs dans les algèbres finies et utilisés dans l'intégration d'une structure prédéfinie au mécanisme général et incrémental de résolution par surréduction contrainte.
43
Penelle, Vincent. "Réécriture d’arbres de piles et traces de systèmes à compteurs." Thesis, Paris Est, 2015. http://www.theses.fr/2015PESC1122/document.
Full textAbstract:
Dans cette thèse, nous nous attachons à étudier des classes de graphes infinis et leurs propriétés, Notamment celles de vérification de modèles, d'accessibilité et de langages reconnus.Nous définissons une notion d'arbres de piles ainsi qu'une notion liée de réécriture suffixe, permettant d'étendre à la fois les automates à piles d'ordre supérieur et la réécriture suffixe d'arbres de manière minimale. Nous définissons également une notion de reconnaissabilité sur les ensembles d'opérations à l'aide d'automates qui induit une notion de reconnaissabilité sur les ensembles d'arbres de piles et une notion de normalisation des ensembles reconnaissables d'opérations analogues à celles existant sur les automates à pile d'ordre supérieur. Nous montrons que les graphes définis par ces systèmes de réécriture suffixe d'arbres de piles possèdent une FO-théorie décidable, en montrant que ces graphes peuvent être obtenu par une interprétation à ensembles finis depuis un graphe de la hiérarchie à piles.Nous nous intéressons également au problème d'algébricité des langages de traces des systèmes à compteurs et au problème lié de la stratifiabilité d'un ensemble semi-linéaire. Nous montrons que dans le cas des polyèdres d'entiers, le problème de stratifiabilité est décidable et possède une complexité coNP-complète. Ce résultat nous permet ensuite de montrer que le problème d'algébricité des traces de systèmes à compteurs plats est décidable et coNP-complet. Nous donnons également une nouvelle preuve de la décidabilité des langages de traces des systèmes d'addition de vecteurs, préalablement étudié par Schwer<br>In this thesis, we study classes of infinite graphs and their properties,especially the model-checking problem, the accessibility problem and therecognised languages.We define a notion of stack trees, and a related notionof ground rewriting, which is an extension of both higher-order pushdownautomata and ground tree rewriting systems. We also define a notion ofrecognisability on the sets of ground rewriting operations through operationautomata. This notion induces a notion of recognisability over sets of stacktrees and a normalisation of recognisable sets of operations, similar to theknown notions over higher-order pushdown automata. We show that the graphsdefined by these ground stack tree rewriting systems have a decidableFO-theory, by exhibiting a finite set interpretation from a graph defined bya higher-order automaton to a graph defined by a ground stack tree rewritingsystem.We also consider the context-freeness problem for counter systems, andthe related problem of stratifiability of semi-linear sets. We prove thedecidability of the stratifiability problem for integral polyhedra and that itis coNP-complete. We use this result to show that the context-freeness problemfor flat counter systems is as well coNP-complete. Finally, we give a new proofof the decidability of the context-freeness problem for vector additionsystems, previously studied by Schwer
44
Gilleron, Rémi. "Reconnaissabilité et fragments décidables en réécriture : automates à piles et calculs de formes normales." Lille 1, 1990. http://www.theses.fr/1990LIL10121.
Full textAbstract:
La réécriture est, à plusieurs titres (programmation fonctionnelle, logico-fonctionnelle équationnelle), un paradigme de la programmation. Notre approche se situe en amont de la programmation et à pour but de contribuer à une meilleure connaissance des arbres et de la réécriture dans les arbres. Nous utilisons, en particulier, la théorie des automates d'arbres. Les résultats principaux de notre travail sont les suivants : 1) nous étudions les problèmes de décidabilité sur les systèmes de réécriture et les forêts reconnaissables. En particulier, nous étudions la propriété (P) : pour toute forêt reconnaissable, l'ensemble des formes normales des termes de F pour S est reconnaissable. Nous prouvons l'indécidabilité de cette propriété. Nous prouvons l'indécidabilité du fragment existentiel de théorie dans l'algèbre des termes clos quotientée par la relation de congruence définie par un ensemble d'équations E, lorsqu'il existe un système de réécriture S convergent, adéquat pour E et satisfaisant (P). Nous présentons un algorithme de décision pour une sous classe de formules linéaires d'une telle théorie ; 2) nous montrons que le problème d'accessibilité est décidable pour les systèmes de réécriture clos modulo la commutativité (complexité polynomiale), est indécidable modulo l'associativité et décidable (résultat partiel) dans le cas associatif et commutatif (équivalent au problème d'accessibilité pour les vecteurs addition systèmes) ; 3) nous introduisons une notion qui permet d'éclairer et de généraliser les études antérieures sur les liens entre systèmes de réécriture et automates à piles.
45
Genet, Thomas. "Contraintes d'ordre et automates d'arbres pour les preuves de terminaison." Nancy 1, 1998. http://docnum.univ-lorraine.fr/public/SCD_T_1998_0245_GENET.pdf.
Full textAbstract:
Les systèmes de réécriture sont des systèmes de calcul simples et lisibles dont l'expressivité est suffisante pour le codage des programmes ou la spécification de processus automatiques. En exprimant les programmes ou processus sous la forme de systèmes de réécriture, on dispose, en outre, d'outils de vérification puissants basés sur les méthodes de preuve de la réécriture. La terminaison assure l'achèvement des calculs en un temps fini et elle est une prémisse indispensable à d'autres méthodes de preuve telle la preuve par récurrence. Classiquement, la preuve de terminaison d'un système de réécriture utilise la recherche d'un ordre bien fondé assurant la décroissance de chaque étape de réécriture. La recherche manuelle d'un tel ordre n'est envisageable que sur des petits systèmes. C'est pourquoi l'automatisation des preuves de terminaison est un élément crucial pour l'exploitation des outils de preuve de la réécriture sur des programmes ou des processus de taille réelle. Dans cette thèse nous présentons deux approches pour l'automatisation des preuves de terminaison des systèmes de réécriture. Dans la première approche, la recherche de l'ordre de terminaison - une instance de l'ordre général sur les chemins (GPO) - est effectuée a l'aide d'un mécanisme de résolution de contraintes d'ordre (sur des graphes orientés) tendant à rendre la recherche efficace et automatique. La deuxième approche est modulaire ; le système est divisé en sous-systèmes et les preuves de terminaison sont réalisées indépendamment pour chaque sous-système. La terminaison du système complet est assurée, pour une certaine stratégie d'application des sous-systèmes, par un critère basé sur le calcul d'une approximation de l'ensemble des formes normales en utilisant des techniques d'automates d'arbres. D'autres applications de cette approximation sont également présentées, parmi lesquelles la complétude suffisante, le test d'atteignabilité, et la preuve de non-terminaison forte.
46
Réty, Pierre. "Méthodes d'unification par surréduction." Nancy 1, 1988. http://www.theses.fr/1988NAN10306.
Full textAbstract:
Introduction. Définitions générales. La surréduction normalisante. La surréduction normalisante basique de gauche à droite. Étude de la minimalité des solutions générées par surréduction. Une approche transformationnelle de la surréduction basique simplifiante. Approche algébrique de la surréduction. Conclusion
47
La, Higuera Colin de. "Fonctions d'arité variable ou infinie : applications aux systèmes d'équations et aux grammaires d'attributs." Bordeaux 1, 1989. http://www.theses.fr/1989BOR10521.
Full textAbstract:
Sont consideres les arbres representant des termes ecrits avec des symboles de fonction d'arite variable ou infinie. Les haies, representant des fermes ou les symboles de fonction prennent une liste d'arguments, sont etudiees. Leurs proprietes de base sont demontrees et la classe des haies regulieres est caracterisee a l'aide d'automates et d'expressions rationnelles. Sont ensuite etudiees les fonctions prenant systematiquement une infinite d'arguments. Enfin, l'etude des grammaires etendues permet de representer de facon plus condensee la syntaxe d'un langage algebrique
48
Oliveira, Kiermes Tavares Claudia Fernanda. "Un système de types pour la programmation par réécriture embarquée." Thesis, Université de Lorraine, 2012. http://www.theses.fr/2012LORR0015/document.
Full textAbstract:
Dans le domaine de l'ingénierie du logiciel, les systèmes de types sont souvent considérés pour la prévention de l'occurrence de termes dénués de sens par rapport à une spécification des types. Dans le cadre de l'extension d'un langage de programmation avec des caractéristiques dédiées, le typage de ces dernières doit être compatible avec les caractéristiques du langage hôte. Cette thèse se situe dans le contexte de la réécriture de termes embarquée dans la programmation orientée objet. Elle vise à développer un système de types avec sous-typage pour le support du filtrage de motifs associatif sur des termes algébriques construits sur des opérateurs variadiques. Ce travail s'appuie sur le langage de réécriture Tom qui fournit des constructions de filtrage de motifs et des stratégies de réécriture à des langages généralistes comme Java. Nous décrivons l'évaluation de code Tom à travers la définition de la sémantique opérationnelle de ce langage en tant qu'élément essentiel de la preuve de la sûreté du système de types. Celui-ci inclut la vérification de types ainsi que l'inférence de types à base de contraintes. Le langage de contraintes est composé d'une part, de contraintes d'égalité, résolues par unification, d'autre part, de contraintes de sous-typage, résolues par la combinaison de phases de simplification, de génération d'une solution et de ramassage de miettes. Le système de types a été intégré au langage Tom, ce qui permet une plus forte expressivité et plus de sûreté a fin d'assurer que les transformations décrites par des règles de réécriture préservent le type des termes<br>In software engineering, type systems are often considered in order to prevent the occurrence of meaningless terms in regard to a type specification. When extending a given programming language with new dedicated features, the typing of these features must be compatible with the ones in the host language. This thesis is situated in the context of term rewriting embedded in object-oriented programming and aims to develop a safe type system featuring subtyping for the support of associative pattern matching on algebraic terms built from variadic operators. In this work we consider the Tom rewriting language that provides associative pattern matching constructs and rewrite strategies for Java. We describe Tom code evaluation through the definition of the operational semantics of the Tom language as an essential element to show that the type system is safe. The type system includes type checking and constraint-based type inference. The constraint language is composed of equality constraints solved by unification and subtyping constraints solved by a combination of simplification, generation of solution and garbage collecting. The type system was integrated in Tom which provides both stronger expressiveness and more safety able to ensure that the transformations described by rewrite rules preserve the type of terms
49
Andrei, Oana-Maria. "Un calcul de réécriture de graphes : applications à la biologie et aux systèmes autonomes." Electronic Thesis or Diss., Vandoeuvre-les-Nancy, INPL, 2008. http://www.theses.fr/2008INPL058N.
Full textAbstract:
L'objectif de cette thèse est d'explorer des descriptions formelles pour la structure et le fonctionnement des systèmes biologiques, ainsi que des outils formels pour raisonner au sujet de leur comportement. Cette thèse s'inscrit dans les travaux étudiant les modèles informatiques sûrs où les calculs sont exprimés par l'intermédiaire de la réécriture, et où nous pouvons compter sur la vérification formelle pour exprimer et valider les propriétés des modèles. Dans cette thèse nous développons un calcul de réécriture d'ordre supérieur pour décrire des molécules, des règles de réaction, et la génération des réseaux biochimiques. Le calcul est basé sur la métaphore chimique en décrivant les calculs en termes de solutions chimiques dans lesquelles les molécules représentant des données agissent l'une sur l'autre librement selon des règles de réaction. Ainsi nous avons obtenu un Calcul Biochimique Abstrait étendant le modèle chimique d'ordre supérieur en considérant des molécules structurées. Le calcul est équipé d'une spécification naturelle de la concurrence et des mécanismes de contrôle grâce à l'expression des stratégies de réécriture sous forme de molécules. La description des complexes moléculaires ou des réactifs chimiques appartient à une classe spécifique de graphes. Nous définissons la structure des graphes avec ports et nous montrons que les principes du calcul biochimique instanciés pour les graphes avec ports sont assez expressifs pour modéliser des systèmes autonomes et des réseaux biochimiques. En plus, les techniques de la réécriture stratégique ouvrent la voie au raisonnement basé sur les calculs et à la vérification des propriétés des systèmes modélisés<br>The objective of this thesis is to explore formal descriptions for the structure and functioning of biological systems, as well as formal tools for reasoning about their behavior. This work takes place in the overall prospective to study safe computational models where computations are expressed via rewriting, and where we can rely on formal verification to express and validate suitable properties. In this thesis we develop a higher-order calculus rewriting for describing molecules, reaction patterns, and biochemical network generation. The calculus is based on the chemical metaphor by describing the computations in terms of chemical solutions in which molecules representing data freely interact according to reaction rules. This way we obtained an Abstract Biochemical Calculus as an extension of the higher-order chemical model by considering structured molecules. The calculus is provided with a natural specification of concurrency and of controlling mechanisms by expressing rewrite strategies as molecules. The description of molecular complexes or chemical reactants belong to specific classes of graphs. We define the structure of port graphs and we show how the principles of the biochemical calculus instantiated for port graphs are expressive enough for modeling autonomous systems and biochemical networks. In addition, strategic rewriting techniques open the way to reason about the computations and to verify properties of the modeled systems
50
Métivier, Yves. "Contribution à l'étude des monoi͏̈des de commutations." Bordeaux 1, 1987. http://www.theses.fr/1987BOR10528.
Full textAbstract:
Le monoide de commutation constitue un rpolongement du monoide libre. Cette structure algebrique dont les elements sont appeles des traces constitue un modele pour l'etude du parallelisme. Trois types de questions sont abordes: la reconnaissabilite d'ensembles de traces, l'approximation des traces et les proprietes de confluence et de terminaison des systemes de reecriture associes a des commutations