Fundamenta Informaticae - Volume 34, issue 3

Authors: Apt, Krzysztof R. | Kirchner, Claude

Article Type: Other

DOI: 10.3233/FI-1998-34306

Citation: Fundamenta Informaticae, vol. 34, no. 3, pp. i-ii, 1998

Authors: Kowalski, Robert A. | Toni, Francesca | Wetzel, Gerhard

Article Type: Research Article

Abstract: We present an extension of Logic Programming (LP) which, in addition to ordinary LP clauses, also includes integrity constraints, explicit representation of disjunction in the bodies of clauses and in goals, and suspension of atoms as in concurrent logic languages. The resulting framework aims to unify Constraint Logic Programming (CLP), Abductive Logic Programming (ALP) and Semantic Query Optimisation (SQO) in deductive databases. We present a proof procedure for the new framework, simplifying and generalising previously proposed proof procedures for ALP. We discuss applications of the framework, formulating traditional problems from LP, ALP, CLP and SQO.

Keywords: Logic Programming (LP), Constraint Logic Programming (CLP), Abductive Logic Programming (ALP), Semantic Query Optimisation (SQO) in Deductive Databases

DOI: 10.3233/FI-1998-34301

Citation: Fundamenta Informaticae, vol. 34, no. 3, pp. 203-224, 1998

Authors: Kirchner, Claude | Ringeissen, Christophe

Article Type: Research Article

Abstract: In this paper we present a view of constraint programming based on the notion of rewriting controlled by strategies. We argue that this concept allows us to describe in a unified way the constraint solving mechanism as well as the meta-language needed to manipulate the constraints. This has the advantage to provide descriptions that are very close to the proof theoretical setting used now to describe constraint manipulations like unification or numerical constraint solving. We examplify the approach by presenting examples of constraint solvers descriptions and combinations written in the ELAN language.

Keywords: Constraint Programming, Constraint Solving, Unification, Rewriting Logic, Computational Systems

DOI: 10.3233/FI-1998-34302

Citation: Fundamenta Informaticae, vol. 34, no. 3, pp. 225-262, 1998

Authors: Castro, Carlos

Article Type: Research Article

Abstract: In this paper, we formalize Constraint Satisfaction Problem manipulation using a rule-based approach. Based on the notion of Computational Systems, we associate basic transformations carried out by traditional constraint solving algorithms with rewrite rules, and heuristics with strategies establishing the order of application of the inferences. In this way, a constraint solver can be viewed as a computational system aimed to transform a set of constraints in a particular solved form. The distinction made between deduction rules and strategies, allows to describe constraint handling in a very abstract way, prototype new heuristics almost by modifying only the choice of rules, …prove termination in an easier way, and combine constraint solving with other computational systems. To validate our approach we have implemented the system COLETTE which is currently executable in ELAN, an environment for prototyping computational systems. We have realized how easy it is to integrate and reuse solvers developed following this approach. We hope that this work leads the way to integrating the knowledge existing in the domains of Automated Deduction and Constraint Solving. Show more

Keywords: Constraint Satisfaction Problems, Rewriting Logic, Computational Systems

DOI: 10.3233/FI-1998-34303

Citation: Fundamenta Informaticae, vol. 34, no. 3, pp. 263-293, 1998

Authors: Apt, Krzysztof R.

Article Type: Research Article

Abstract: We provide here a proof theoretic account of constraint programming that attempts to capture the essential ingredients of this programming style. We exemplify it by presenting proof rules for linear constraints over interval domains, and illustrate their use by analyzing the constraint propagation process for the SEND + MORE = MONEY puzzle. We also show how this approach allows one to build new constraint solvers.

Keywords: constraints, constraint propagation, proof rules, linear constraints

DOI: 10.3233/FI-1998-34304

Citation: Fundamenta Informaticae, vol. 34, no. 3, pp. 295-321, 1998

Authors: Réty, Jean-Hugues

Article Type: Research Article

Abstract: We investigate the problem of building distributed systems within the Concurrent Constraint programming framework (CC). CC languages form a shared memory constraint-based model of calculus and some of its main features, especially the global nature of the store and the communication mechanism, are impediments to distributed implementation. We think it to be necessary to introduce some new features in CC languages to build up a language suitable for distributed programming. We first discuss the solutions previously studied within the Logic Programming framework. Then, we propose the introduction of an asynchronous message-based communication mechanism. It smoothly integrates within CC, constraints allowing …for a logical formulation of message-based communication, and induces notions of local computation, local store, and site. Show more

Keywords: Distributed languages, Concurrent languages, Concurrent Constraint languages

DOI: 10.3233/FI-1998-34305

Citation: Fundamenta Informaticae, vol. 34, no. 3, pp. 323-346, 1998