We present a procedure for partial deduction of logic programs, based on an automatic unfolding algorithm which guarantees the construction of sensibly and strongly expanded, finite SLD-trees. We prove that the partia...
详细信息
We present a procedure for partial deduction of logic programs, based on an automatic unfolding algorithm which guarantees the construction of sensibly and strongly expanded, finite SLD-trees. We prove that the partial deduction procedure terminates for all definite logic programs and queries. We show that the resulting program satisfies important soundness and completeness criteria with respect to the original program, while retaining the essentially desired amount of specialisation.
the specification and derivation of substitution for the de Bruijn representation of h-terms is used to illustrate programming with a function-sequence monad. the resulting program is improved by interactive program t...
详细信息
the specification and derivation of substitution for the de Bruijn representation of h-terms is used to illustrate programming with a function-sequence monad. the resulting program is improved by interactive program transformation methods into an efficient implementation that uses primitive machine arithmetic. these transformations illustrate new techniques that assist the discovery of the arithmetic structure of the solution.
We introduce a constraint system called FT. this system offers a theoretical and practical alternative to the usual Herbrand system of constraints over constructor trees. Like Herbrand, FT provides a universal data st...
详细信息
We introduce a constraint system called FT. this system offers a theoretical and practical alternative to the usual Herbrand system of constraints over constructor trees. Like Herbrand, FT provides a universal data structure based on trees. However, the trees of FT (called feature trees) are more general than the constructor trees of Herbrand, and the constraints of FT are of finer grain and of different expressiveness. the essential novelty of FT is provided by functional attributes called features which allow representing data as extensible records, a more flexible way than that offered by Herbrand's fixed arity constructors. the feature tree structure determines an algebraic semantics for FT. We establish a logical semantics, thanks to three axiom schemes presenting the first-order theory FT. We propose using FT as a constraint system for logicprogramming. We provide a test for constraint unsatisfiability, and a test for constraint entailment. the former corresponds to unification and the latter to matching. the combination of the two is needed for advanced control mechanisms. We use the concept of relative simplification of constraints, a normalization process that decides entailment and unsatisfiability simultaneously. the two major technical contributions of this work are: (i) an incremental system performing relative simplification for FT that we prove to be sound and complete;and (ii) a proof showing that FT satisfies independence of negative constraints, the property that conjoined negative constraints may be handled independently.
this conference proceedings contains 10 papers. Topics covered include: compositional semantics for logic programs;closed-world assumptions to well-founded semantics;logic program synthesis;realizability interpretatio...
详细信息
this conference proceedings contains 10 papers. Topics covered include: compositional semantics for logic programs;closed-world assumptions to well-founded semantics;logic program synthesis;realizability interpretation of coninductive definitions and program synthesis with streams;defining concurrent processes;an abstract machine for concurrent modular sytems;computer programming language MLOG;duality of abduction and model generation;and, feature constraint system for logicprogramming.
this paper considers open logic programs originally introduced as a tool to build an OR-compositional semantics of logic programs. We extend the original semantic definitions in the framework of the general approach t...
详细信息
this paper considers open logic programs originally introduced as a tool to build an OR-compositional semantics of logic programs. We extend the original semantic definitions in the framework of the general approach to the semantics of logic programs described by Gabbrielli and Levi (1991). We first define an operational semantics O-Omega(P) which models computed answer substitutions and which is compositional w.r.t. the union of programs. Next, we consider the semantic domain of Omega-denotations, which are sets of clauses with a suitable equivalence relation. the fixpoint semantics F-Omega(P) given by Bossi and Menegus (1991) is proved equivalent to the operational semantics. From the model-theoretic viewpoint, an Omega-denotation is mapped onto a set of Herbrand interpretations, thus leading to a definition of an Omega-model based on the classical notion of truth. Moreover, we consider a particular kind of Omega-models (compositional models), and we show that O-Omega,(P) is a (nonminimal) compositional Omega-model. A suitable abstraction of O-Omega,(P) is compositional and fully abstract w.r.t. the equivalence induced by successful derivations. Finally, some applications of our semantics are discussed. In particular, O-Omega,(P) can be viewed as the foundation of modular program analysis.
the main aim of the paper is to construct a logical system in which properties of programs can be formalized for verification, synthesis and transformation. the paper has two main points. One point is a realizability ...
详细信息
the main aim of the paper is to construct a logical system in which properties of programs can be formalized for verification, synthesis and transformation. the paper has two main points. One point is a realizability interpretation of coinductive definitions of predicates. the other point is extraction of programs which treat streams. An untyped predicative theory TIDv is presented, which has the facility of coinductive definitions of predicates and is based on constructive logic. Properties defined by the greatest fixed point, such as streams and the extensional equality of streams, can be formalized by the facility of coinductive definitions of predicates in TIDv. A q-realizability interpretation for TIDv is defined and the soundness of the interpretation is proved. By the realizability interpretation, a program which treats streams can be extracted from a proof of its specification in TIDv. A general program extraction theorem and a stream program extraction theorem are presented.
the proceedings contain 33 papers. the special focus in this conference is on programming. the topics include: Local type reconstruction by means of symbolic fixed point iteration;an asynchronous process algebra with ...
ISBN:
(纸本)9783540578802
the proceedings contain 33 papers. the special focus in this conference is on programming. the topics include: Local type reconstruction by means of symbolic fixed point iteration;an asynchronous process algebra with multiple clocks;foundational issues in implementing constraint logicprogramming systems;characterizing behavioural semantics and abstractor semantics;simulation of SOS definitions with term rewriting systems;strategies in modular system design by interface rewriting;symbolic model checking and constraint logicprogramming: a crossfertilization;a logical denotational semantics for constraint logicprogramming;compilation of head and strong reduction;suffix trees in the functional programming paradigm;suffix trees in the functional programming paradigm;symbolic model checking and constraint logicprogramming: a crossfertilization;a logical denotational semantics for constraint logicprogramming;compilation of head and strong reduction;suffix trees in the functional programming paradigm;a logical denotational semantics for constraint logicprogramming;compilation of head and strong reduction;suffix trees in the functional programming paradigm;type classes in Haskell;lazy type inference for the strictness analysis of lists;lazy unification with simplification;polymorphic binding-time analysis;shapely types and shape polymorphism;first-class polymorphism for ml;dimension types;a synergistic analysis for sharing and groundness which traces linearity;a logical framework for evolution of specifications;a semantics for higher-order functors;an abstract machine for sound evaluation of parallel functional programs with first-class continuations;a tiny constraint functional logic language and its continuation semantics;fully abstract translations and parametric polymorphism.
Given a program P we specify an enlargement of its well-founded model which gives meaning to the adding of closed world assumptions. We do so by proposing the desirable principles of a closed world assumption (CWA), a...
详细信息
Given a program P we specify an enlargement of its well-founded model which gives meaning to the adding of closed world assumptions. We do so by proposing the desirable principles of a closed world assumption (CWA), and proceed to formally define and apply them to well-founded semantics (WFS), in order to obtain a WFS added with CWA, the O-semantics. After an introduction and motivating examples, there follow the presentation of the concepts required to formalize the model structure, the properties it enjoys, and the criteria and procedures which allow the precise characterization of the preferred unique maximal model that gives the intended meaning to the O-semantics of a program, the O-model. Some properties are also exhibited that permit a more expedite obtention of the models. Several detailed examples are introduced throughout to illustrate the concepts and their application. Comparison is made with other work, and in the conclusions the novelty of the approach is brought out.
We present a duality relationship between abduction for definite abductive programs and model generation on the only-if part of these programs. As was pointed out by Console et al. (1991), abductive solutions for an a...
详细信息
We present a duality relationship between abduction for definite abductive programs and model generation on the only-if part of these programs. As was pointed out by Console et al. (1991), abductive solutions for an abductive program correspond to models of the only-if part. We extend this observation by showing that the procedural semantics of abduction itself can be interpreted dually as a form of model generation on the only-if part. this model generation extends Satchmo with an efficient treatment of equality atoms occurring in the head of rules. It is illustrated how this duality allows to improve current procedures for both abduction and model generation by transferring technical results known for one of these computational paradigms to the other.
the Concurrent Constraint programming paradigm has been the subject of growing interest as the focus of a new paradigm for concurrent computation. Like logicprogramming it claims close relations to logic. In fact the...
详细信息
暂无评论