Book Description
CE TRAVAIL PORTE SUR L'INTEGRATION DES CONTRAINTES SYMBOLIQUES SUR DES ENSEMBLES HEREDITAIREMENT FINIS DANS LES LANGAGES DE PROGRAMMATION EN LOGIQUE, CONFORMEMENT AU MODELE CLP (CONSTRAINT LOGIC PROGRAMMING). NOUS DEFINISSONS DANS CETTE THESE LA STRUCTURE D'UN LANGAGE DE PROGRAMMATION EN LOGIQUE AVEC CONTRAINTES SUR DES ENSEMBLES HEREDITAIREMENT FINIS (CLPS), DISPOSANT DES OPERATEURS D'EGALITE, D'APPARTENANCE, DE NON-APPARTENANCE, D'INCLUSION ET ENFIN, D'UNION ET D'INTERSECTION. NOUS MONTRONS QUE LE MODELE STANDARD DE LA PROGRAMMATION EN LOGIQUE (UNIFICATION DANS L'UNIVERS DE HERBRAND) EST INADAPTE EN RAISON DU CARACTERE NP-COMPLET DE L'UNIFICATION ENSEMBLISTE. NOUS PROPOSONS AU TRAVERS DE CLPS UNE APPROCHE DIFFERENTE FONDEE NON PLUS SUR L'UNIFICATION, MAIS SUR LE CONTROLE DE CONSISTANCE DES CONTRAINTES. LE PROTOTYPE CLPS A ENTIEREMENT ETE DEVELOPPE EN PROLOG. IL IMPLANTE D'UNE PART DES ALGORITHMES DE CONSISTANCE PARTIELLE SPECIFIQUE AUX CONTRAINTES ENSEMBLISTES, D'AUTRE PART DES ALGORITHMES D'ENUMERATION DES VALEURS CAPABLES DE RESOUDRE LES CONTRAINTES ENSEMBLISTES. DANS CE CONTEXTE, L'UNIFICATION ENSEMBLISTE EST VUE COMME UNE CONTRAINTE D'EGALITE, QUI A LA MANIERE DES AUTRES CONTRAINTES ENSEMBLISTES, EST RETARDEE TANT QU'IL N'EST PAS POSSIBLE DE LA RESOUDRE DE MANIERE DETERMINISTE. NOUS UTILISONS LE LANGAGE CLPS POUR RESOUDRE UN PROBLEME INDUSTRIEL DE GENIE LOGICIEL (BANC DE VALIDATION)
Book Description
LES TECHNIQUES DE SATISFACTION DE CONTRAINTES ONT ETE RECEMMENT INTRODUITES EN PROGRAMMATION LOGIQUE EN VUE D'ETENDRE LE DOMAINE D'APPLICATION DES LANGAGES DE PROGRAMMATION EN LOGIQUE. LES LANGAGES EXISTANTS, BASES SUR CES TECHNIQUES, CONSIDERENT DES CONTRAINTES ARITHMETIQUES APPLIQUEES A DES VARIABLES PRENANT LEUR VALEUR DANS DES DOMAINES D'ENTIERS. CELA REND DIFFICILE UNE MODELISATION CONCISE ET NATURELLE AINSI QU'UNE RESOLUTION EFFICACE DE CERTAINS PROBLEMES COMBINATOIRES NP-COMPLETS, DE NATURE ENSEMBLISTE. NOUS PROPOSONS UNE SOLUTION QUI CONSISTE A ETENDRE LA NOTION DE DOMAINE D'ENTIERS A CELLE DE DOMAINE ENSEMBLISTE (ENSEMBLE D'ENSEMBLES). NOUS SPECIFIONS UN DOMAINE ENSEMBLISTE PAR UN INTERVALLE DONT LES BORNES INFERIEURE ET SUPERIEURE SONT DES ENSEMBLES CONNUS, ORDONNES PAR L'INCLUSION ENSEMBLISTE. NOUS DEFINISSONS LA STRUCTURE FORMELLE ET CONCRETE D'UN NOUVEAU LANGAGE DE PROGRAMMATION EN LOGIQUE PAR CONTRAINTES SUR DOMAINES ENSEMBLISTES, APPELE CONJUNTO. CONJUNTO COMPREND LES SYMBOLES D'OPERATIONS ENSEMBLISTES USUELS (,, /) INTERPRETES SOUS UNE FORME RELATIONNELLE (S S#1 = S#2,) ET LA RELATION D'INCLUSION (). DE PLUS IL POURVOIT UN ENSEMBLE DES CONTRAINTES APPELEES CONTRAINTES GRADUEES (EX. FONCTION DE CARDINALITE) QUI ASSOCIENT A UN ENSEMBLE UN TERME ARITHMETIQUE. CELA NOUS PERMET DE TRAITER LES PROBLEMES D'OPTIMISATION EN APPLIQUANT UNE FONCTION DE COUT AUX TERMES MESURABLES, I.E. ARITHMETIQUES, ASSOCIES AUX TERMES ENSEMBLISTES. LA RESOLUTION DES CONTRAINTES DANS CONJUNTO EST BASEE SUR DES TECHNIQUES DE SATISFACTION DE CONTRAINTES PAR REDUCTION D'INTERVALLES ETENDUES AU TRAITEMENT DES CONTRAINTES ENSEMBLISTES. AINSI, LA CONTRIBUTION PRINCIPALE DE CETTE THESE CONCERNE LA DEFINITION DE REGLES DE TRANSFORMATION AU SEIN D'UN ALGORITHME GENERIQUE, QUI INFERENT LA CONSISTANCE LOCALE DES CONTRAINTES DU LANGAGE EN REDUISANT LES INTERVALLES ENSEMBLISTES. UN ENSEMBLE D'APPLICATIONS DE RECHERCHE OPERATIONNELLE ET DE MATHEMATIQUES COMBINATOIRES ONT ETE DEVELOPPEES AVEC CONJUNTO, ILLUSTRANT AINSI LES FORCES DU LANGAGE EN TERME DE RAPPORT EXPRESSIVITE/EFFICACITE
Book Description
Les travaux présentés dans cette thèse proposent une méthode originale de génération automatique de tests fonctionnels aux limites accompagnée d'un environnement baptisé BZ-Testing-Tools. Le but de notre démarche est de générer des jeux de tests à partir d'une machine abstraite B du système sous test produite spécialement pour la phase de test. Cette méthode repose sur la réécriture de la spécification B en un système de contraintes et la partition du domaine des variables de la spécification, ce qui permet d'exhiber l'ensemble des comportements du système. A partir de chaque comportement, des entrées de test aux limites sont calculées au moyen d'un solveur spécifique utilisant des techniques de Programmation Logique avec Contraintes. Des séquences de tests sont alors générées par parcours du graphe d'atteignabilité de la spécification. La vérification des résultats de l'exécution est effectuée par comparaison des états de sortie avec ceux obtenus par animation du modèle abstrait.
Book Description
Dans cette thèse, notre contribution s'inscrit dans le cadre du projet CLPS qui vise a inclure les ensembles comme structures à part entière dans un langage de programmation logique. Le langage CLPS propose des techniques de résolution de contraintes ensemblistes sur les structures d'ensemble, multi-ensemble et séquence. Cette dernière dénote une structure ordonnée définie sur une collection d'objets connus et soumise à un ensemble de contraintes de groupe, de précédence et métriques. Un premier résultat de recherche consiste en une proposition d'extension de la structure de séquence afin d'autoriser sa définition sur les éléments d'une partie seulement d'un ensemble connu. Nous définissons ainsi une nouvelle structure ensembliste ordonnée appelée séquence partielle. Elle permet, par exemple, de traiter des problèmes d'ordonnancement où l'on ne connaît pas a priori les tâches à ordonnancer. Celles-ci seront sélectionnées selon des critères décrits par les contraintes du problème à résoudre. Nous associons à la structure de séquence partielle un modèle théorique à base d'arbre PQR mais autorisant la greffe de nouvelles feuilles sur la racine de cet arbre. Nous présentons dans le second volet de ce mémoire des fonctions spécifiques offrant la possibilité de définir des critères mesurables de sélection des éléments devant appartenir à une structure ensembliste. Ces fonctions, appelées fonctions graduées et interprétées comme des contraintes, permettent d'associer à un terme non mesurable, en l'occurrence un ensemble, une variable entière représentant une mesure de ce terme. La variable entière supporte des relations d'arithmétique linéaire, dont la résolution permet de réduire l'espace de recherche de la variable ensembliste. Des problèmes de partitionnement d'ensembles, tels que le Bin-packing par exemple, ont pu être efficacement résolus en utilisant les fonctions graduées.
Book Description
Dans cette thèse, nous avons défini une approche fondée sur des techniques de Satisfaction de Contraintes Ensemblistes pour l'évaluation de spécifications formelles logico-ensemblistes, type B. Nous montrons en particulier comment dans ce paradigme, il est possible de conserver le non déterminisme de la spécification. L'évaluation des expressions B avec des contraintes ensemblistes constitue une problématique nouvelle amenant à résoudre : le calcul des formules ensemblistes, relations et fonctions, le calcul des substitutions et la vérification de l'invariant. Cette recherche a conduit à développer un solveur ensembliste spécifique utilisant une représentation énumérative des domaines. Ces domaines sont représentés par des ensembles de constantes mais également de variables. Cette représentation est induite par les contraintes engendrées durant l'évaluation de la spécification. Des règles d'inférences spécifiques ont alors été définies pour assurer une propagation efficace dans ce contexte particulier. Une implémentation du solveur a été réalisée : CLPS-B...
Author: Agostino Dovier Publisher: Springer Science & Business Media ISBN: 3642143083 Category : Computers Languages : en Pages : 342
Book Description
This book celebratesthe 25th anniversaryof GULP—the Italian Associationfor LogicProgramming.Authored by Italian researchersat the leading edge of their ?elds, it presents an up-to-date survey of a broad collection of topics in logic programming, making it a useful reference for both researchers and students. During its 25-year existence, GULP has organised a wide range of national and international activities, including both conferences and summer schools. It has been especially active in supporting and encouraging young researchers, by providing scholarships for GULP events and awarding distinguished disser- tions. WeintheinternationallogicprogrammingcommunitylookuponGULPwith a combination of envy, admiration and gratitude. We are pleased to attend its conferences and summer schools, where we can learn about scienti?c advances, catch up with old friends and meet young students. It is an honour for me to acknowledge our appreciation to GULP for its outstanding contributions to our ?eld and to express our best wishes for its continuing prosperity in the future. March 2010 Robert Kowalski Imperial College London Preface On June 18, 1985, a group of pioneering researchers, including representatives from industry, national research labs, and academia, attended the constituent assembly of the Group of researchers and Users of Logic Programming (GULP) association. That was the starting point of a long adventure in science, that 1 we are still experiencing 25 years later. This volume celebrates this important event.
Author: Ricardo Caferra Publisher: Springer Science & Business Media ISBN: 3540671900 Category : Computers Languages : en Pages : 306
Book Description
This volume presents a collection of thoroughly reviewed revised full papers on automated deduction in classical, modal, and many-valued logics, with an emphasis on first-order theories. Five invited papers by prominent researchers give a consolidated view of the recent developments in first-order theorem proving. The 14 research papers presented went through a twofold selection process and were first presented at the International Workshop on First-Order Theorem Proving, FTP'98, held in Vienna, Austria, in November 1998. The contributed papers reflect the current status in research in the area; most of the results presented rely on resolution or tableaux methods, with a few exceptions choosing the equational paradigm.
Author: Jean Goubault-Larrecq Publisher: Springer Science & Business Media ISBN: 9781402003684 Category : Computers Languages : en Pages : 448
Book Description
Interest in computer applications has led to a new attitude to applied logic in which researchers tailor a logic in the same way they define a computer language. In response to this attitude, this text for undergraduate and graduate students discusses major algorithmic methodologies, and tableaux and resolution methods. The authors focus on first-order logic, the use of proof theory, and the computer application of automated searches for proofs of mathematical propositions. Annotation copyrighted by Book News, Inc., Portland, OR
Author: Srinivas Bangalore Publisher: Bradford Books ISBN: 9780262013871 Category : Computers Languages : en Pages : 0
Book Description
Investigations into employing statistical approaches with linguistically motivated representations and its impact on Natural Language processing tasks. The last decade has seen computational implementations of large hand-crafted natural language grammars in formal frameworks such as Tree-Adjoining Grammar (TAG), Combinatory Categorical Grammar (CCG), Head-driven Phrase Structure Grammar (HPSG), and Lexical Functional Grammar (LFG). Grammars in these frameworks typically associate linguistically motivated rich descriptions (Supertags) with words. With the availability of parse-annotated corpora, grammars in the TAG and CCG frameworks have also been automatically extracted while maintaining the linguistic relevance of the extracted Supertags. In these frameworks, Supertags are designed so that complex linguistic constraints are localized to operate within the domain of those descriptions. While this localization increases local ambiguity, the process of disambiguation (Supertagging) provides a unique way of combining linguistic and statistical information. This volume investigates the theme of employing statistical approaches with linguistically motivated representations and its impact on Natural Language Processing tasks. In particular, the contributors describe research in which words are associated with Supertags that are the primitives of different grammar formalisms including Lexicalized Tree-Adjoining Grammar (LTAG). Contributors Jens Bäcker, Srinivas Bangalore, Akshar Bharati, Pierre Boullier, Tomas By, John Chen, Stephen Clark, Berthold Crysmann, James R. Curran, Kilian Foth, Robert Frank, Karin Harbusch, Sasa Hasan, Aravind Joshi, Vincenzo Lombardo, Takuya Matsuzaki, Alessandro Mazzei, Wolfgang Menzel, Yusuke Miyao, Richard Moot, Alexis Nasr, Günter Neumann, Martha Palmer, Owen Rambow, Rajeev Sangal, Anoop Sarkar, Giorgio Satta, Libin Shen, Patrick Sturt, Jun'ichi Tsujii, K. Vijay-Shanker, Wen Wang, Fei Xia
Author: EMMANUEL.. LEGROS
Author: CARMEN.. GERVET
Author: Fabien Peureux
Author: Lotfi Berkaoui
Author: Fabrice Ambert
Author: Laurent Py
Author: Agostino Dovier
Author: Ricardo Caferra
Author: Jean Goubault-Larrecq
Author: Srinivas Bangalore