In this paper we present an overview of the unfold/fold proof method, a method for proving theorems about programs, based on program transformation. As a metalanguage for specifying programs and program properties we ...
详细信息
In this paper we present an overview of the unfold/fold proof method, a method for proving theorems about programs, based on program transformation. As a metalanguage for specifying programs and program properties we adopt constraint logic programming (CLP), and we present a set of transformation rules (including the familiar unfolding and folding rules) which preserve the semantics of CLP programs. Then, we show how program transformation strategies can be used, similarly to theorem proving tactics, for guiding the application of the transformation rules and inferring the properties to be proved. We work out three examples: (i) the proof of predicate equivalences, applied to the verification of equality between CCS processes, (ii) the proof of first order formulas via an extension of the quantifier elimination method, and (iii) the proof of temporal properties of infinite state concurrent systems, by using a transformation strategy that performs program specialization.
Let L(X )be the language of a first-order, decidable, quantifier-free theory X. Consider the language, L-RQ(X), that extends L-X with formulas of the form for all x is an element of A : phi (restricted universal quant...
详细信息
Let L(X )be the language of a first-order, decidable, quantifier-free theory X. Consider the language, L-RQ(X), that extends L-X with formulas of the form for all x is an element of A : phi (restricted universal quantifier, RUQ) and there exists x is an element of A : phi(restricted existential quantifier, REQ), where A is a finite set and phi is a formula made of X-formulas, RUQ and REQ. That is,L-RQ(X)admits nested restricted quantifiers. In this paper we present a decision procedure for some expressive fragments of L-RQ(X) and its implementation as part of the{log}('setlog') tool. The usefulness of the approach is shown by reporting on three real-world case studies.
The transformation of constraintlogic programs (CLP programs) has been shown to be an effective methodology for verifying properties of imperative programs. By following this methodology, we encode the negation of a ...
详细信息
The transformation of constraintlogic programs (CLP programs) has been shown to be an effective methodology for verifying properties of imperative programs. By following this methodology, we encode the negation of a partial correctness property of an imperative program progas a predicate incorrect defined by a CLP program T, and we show that prog is correct by transforming T into the empty program (and thus incorrect does not hold) through the application of semantics preserving transformation rules. We can also show that prog is incorrect by transforming T into a program with the fact incorrect (and thus incorrect does hold). Some of the transformation rules perform replacements of constraints that are based on properties of the data structures manipulated by the program prog. In this paper we show that constraint Handling Rules (CHR) are a suitable formalism for representing and applying constraint replacements during the transformation of CLP programs. In particular, we consider programs thatmanipulate integer arrays and we present a CHR encoding of a constraint replacement strategy based on the theory of arrays. We also propose a novel generalization strategy for constraints on integer arrays that combines CHR constraint replacements with various generalization operators on integer constraints, such as widening and convex hull. Generalization is controlled by additional constraints that relate the variable identifiers in the imperative program prog and the CLP representation of their values. The method presented in this paper has been implemented and we have demonstrated its effectiveness on a set of benchmark programs taken from the literature.
Tabled constraint logic programming is a powerful execution mechanism for dealing with constraint logic programming without worrying about fixpoint computation. Various applications, e.g. in the fields of program anal...
详细信息
Tabled constraint logic programming is a powerful execution mechanism for dealing with constraint logic programming without worrying about fixpoint computation. Various applications, e.g. in the fields of program analysis and model checking, have been proposed. Unfortunately, a high-level system for developing new applications is lacking, and programmers are forced to resort to complicated ad hoc solutions. This papers presents TCHR, a high-level framework for tabled constraint logic programming. It integrates in a light-weight manner constraint Handling Rules (CHR), a high-level language for constraint solvers, with tabled logicprogramming. The framework is easily instantiated with new application-specific constraint domains. Various high-level operations can be instantiated to control performance. In particular, we propose a novel, generalized technique for compacting answer sets.
Abductive logicprogramming (ALP) has been proven very effective for formalizing societies of agents, commitments and norms, in particular by mapping the most common deontic operators (obligation, prohibition, permiss...
详细信息
Abductive logicprogramming (ALP) has been proven very effective for formalizing societies of agents, commitments and norms, in particular by mapping the most common deontic operators (obligation, prohibition, permission) to abductive expectations. In our previous works, we have shown that ALP is a suitable framework for representing norms. Normative reasoning and query answering were accommodated by the same abductive proof procedure, named SCIFF. In this work, we introduce a defeasible flavour in this framework, in order to possibly discharge obligations in some scenarios. Abductive expectations can also be qualified as dischargeable, in the new, extended syntax. Both declarative and operational semantics are improved accordingly, and proof of soundness is given under syntax allowedness conditions. Moreover, the dischargement itself might be proved invalid, or incoherent with the rules, due to new knowledge provided later on. In such a case, a discharged expectation might be reinstated and hold again after some evidence is given. We extend the notion of dischargement to take into consideration also the reinstatement of expectations. The expressiveness and power of the extended framework, named SCIFFD, is shown by modeling and reasoning upon a fragment of the Japanese Civil Code. In particular, we consider a case study concerning manifestations of intention and their rescission (Section II of the Japanese Civil Code).
The paper investigates a novel approach, based on constraint logic programming (CLP), to predict the 3D conformation of a protein via fragments assembly. The fragments are extracted by a preprocessor-also developed fo...
详细信息
The paper investigates a novel approach, based on constraint logic programming (CLP), to predict the 3D conformation of a protein via fragments assembly. The fragments are extracted by a preprocessor-also developed for this work-from a database of known protein structures that clusters and classifies the fragments according to similarity and frequency. The problem of assembling fragments into a complete conformation is mapped to a constraint solving problem and solved using CLP. The constraint-based model uses a medium discretization degree C alpha-side chain centroid protein model that offers efficiency and a good approximation for space filling. The approach adapts existing energy models to the protein representation used and applies a large neighboring search strategy. The results shows the feasibility and efficiency of the method. The declarative nature of the solution allows to include future extensions, e.g., different size fragments for better accuracy.
Negation has traditionally been a difficult issue in logicprogramming. Most of Prolog programmers have been restricted to use just a weak negation technique, like negation as failure. Many alternative semantics were ...
详细信息
Negation has traditionally been a difficult issue in logicprogramming. Most of Prolog programmers have been restricted to use just a weak negation technique, like negation as failure. Many alternative semantics were proposed for achieving constructive negation in the last 20 years, but no implementation was provided so far because of its exponential complexity and the difficulty for developing it. First effective implementations of constructive negation into standard Prolog compilers are available just recently, around 2003, provided by our previous works. In this paper we present an extension of our implementations by introducing types in programs, thus improving usability as well as efficiency in some cases of our implementations of constructive negation. This can make constructive negation an interesting approach for its use in data bases querying, web search, filtered search, ontologies querying, coding rules, business rules, etc. Thanks to the use of types, our constructive negation can provide concrete values as results, instead of constraints (as in our previous works). We provide details about the semantics and the implementation in our approaches of classical, finite constructive, and intensional negation. The paper also includes some practical examples additionally allowing for providing measurements of computational behavior.
The paper presents an optimization model and its implementation using a hybrid approach for the Capacitated Vehicle Routing Problem with Pick-up and Alternative Delivery (CVRPPAD). The development of the CVRPPAD was m...
详细信息
The paper presents an optimization model and its implementation using a hybrid approach for the Capacitated Vehicle Routing Problem with Pick-up and Alternative Delivery (CVRPPAD). The development of the CVRPPAD was motivated by postal items distribution issues. The model proposed combines various features of Vehicle Routing Problem variants. The novelty of this model lies in the introduction of alternativeness of item delivery points, differentiation of delivery point types in terms of their capacity (parcel lockers) and possibility of collecting the items during the execution of delivery routes. The model also takes into account a possibility of introducing time windows related to delivery time. The proposed data structure in the form of sets of facts facilitates the implementation of the model in all environments, constraint logic programming (CLP), Mathematical programming (MP), metaheuristics, databases, etc. The model is implemented in the MP, hybrid CLP/MP, and hybrid CLP/heuristic environments. The hybrid CLP/MP approach is the authors' original solution, which has already been used to solve Supply Chain Management problems, scheduling problems, routing problems etc. For large size problems, considering their combinatorial character, the proposed CLP/MP approach is ineffective. Its effectiveness will improve when MP is replaced by a heuristic. All implementations were performed on the same data instances (facts), which made it possible to compare them according to the solution search time, number of decision variables and number of constraints. The directions into which the model can be further developed were also presented.
Behaviour is a reflection of a reasoning process that must deal with constraints imposed by an external environment, internal knowledge and physical structure. This paper proposes a framework for behavioural animation...
详细信息
Behaviour is a reflection of a reasoning process that must deal with constraints imposed by an external environment, internal knowledge and physical structure. This paper proposes a framework for behavioural animation that is based on the next generation of object-oriented, constraint-based expert systems technology, and applies a control structure of knowledge agents and knowledge units to determine the behaviour of objects to be animated. Knowledge agents are responsible for planning, plan implementation and information extraction from the environment. The activity of an agent is dependent on the knowledge units ascribed to them by the animator. The interaction between agents and knowledge units is resolved by the reasoning engine, and thus, influences the eventual motion displayed. An example given in NSAIL, a pilot implementation using the model-based ECHIDNA constraint logic programming shell. With this approach, the motion for a sailing scenario and other behavioural domains can be specified at a high level through the characterization of the knowledge agents.
We present a prescriptive type system with parametric polymorphism and subtyping for constraintlogic programs. The aim of this type system is to detect programming errors statically. It introduces a type discipline f...
详细信息
We present a prescriptive type system with parametric polymorphism and subtyping for constraintlogic programs. The aim of this type system is to detect programming errors statically. It introduces a type discipline for constraintlogic programs and modules, while maintaining the capabilities of performing the usual coercions between constraint domains. and of typing meta-programming predicates, thanks to the flexibility of subtyping. The property of subject reduction expresses the consistency of a prescriptive type system w.r.t. the execution model: if a program is 'well-typed'. then all derivations starting from a 'well-typed' goat are again 'well-typed'. That property is proved w.r.t. the abstract execution model of constraintprogramming which proceeds by accumulation of constraints only. and w.r.t. an enriched execution model with type constraints for substitutions. We describe our implementation of the system for type checking and type inference. We report our experimental results on type checking ISO-Prolog, the (constraint) libraries of Sicstus Prolog and other Prolog programs.
暂无评论