Canonical logic programs

Consider the class of programs P where the greatest fixpoint of T_P is equal to the complement of the finite failure set of P. Programs in this calss possess some important properties which others do not. The main result in this paper proves that this class is representative of all programs. Specifically, we call the programs in this class canonical and we prove that for any program P₁, there exists a semantically equivalent program P₂ which is canonical.     

Nested expressions in logic programs

We extend the answer set semantics to a class of logic programs with nested expressions permitted in the bodies and heads of rules. These expressions are formed from literals using negation as failure, conjunction (,) and disjunction (;) that can be nested arbitrarily. Conditional expressions are introduced as abbreviations. The study of equivalent transformations of programs with nested expressions shows that any such program is equivalent to a set of disjunctive rules, possibly with negation as failure in the heads. The generalized answer set semantics is related to the Lloyd–Topor generalization of Clark’s completion and to the logic of minimal belief and negation as failure. This revised version was published online in June 2006 with corrections to the Cover Date.     

Hypothetical reasoning in logic programs

In order to express incomplete knowledge, extended logic programs have been proposed as logic programs with classical negation along with negation as failure. This paper discusses ways to deal with a broad class of common sense knowledge by using extended logic programs. For this purpose, we present a uniform approach for dealing with both incomplete and contradictory programs, as a simple framework of hypothetical reasoning in which some rules are dealt with as candidate hypotheses that can be used to augment the background theory. This theory formation framework can be used for default reasoning, contradiction removals, the closed world assumption, and abduction. We also show a translation of the theory formation framework to an extended logic program whose answer sets correspond to the consistent belief sets of augmented theories.     

Equivalent logic programs and symmetric homogeneous forms of logic programs with equality

This article introduces the notion of CAS-equivalent logic programs: logic programs with identical correct answer substitutions. It is shown that the notions CAS-equivalence, refutational equivalence, and logical equivalence do not coincide in the case of definite clause logic programs. Least model criteria for refutational and CAS-equivalence are suggested and their correctness is proved. The least model approach is illustrated by two proofs of CAS-equivalence. It is shown that the symmetric extension of a logic program subsumes the symmetry axiom and the symmetric homogeneous form of a logic program with equality subsumes the symmetry, transitivity, and predicate substitutivity axioms of equality. These results contribute towards the goal of building equality into standard Prolog without introducing additional inference rules.     

Most specific logic programs

More specific versions of definite logic programs are introduced. These are versions of a program in which each clause is further instantiated or removed and which have an equivalent set of successful derivations to those of the original program, but a possibly increased set of finitely failed goals. They are better than the original program because failure in a non-successful derivation may be detected more quickly. Furthermore, information about allowed variable bindings which is hidden in the original program may be made explicit in a more specific version of it. This allows better static analysis of the program's properties and may reveal errors in the original program. A program may have several more specific versions but there is always a most specific version which is unique up to variable renaming. Methods to calculate more specific versions are given and it is characterized when they give the most specific version.     

Transformations of logic programs

This paper introduces a new concept of computation trees of logic programs that will be used in reasoning about programs. Three types of transformations improving the structure of logic programs are described. There are two natural measures of complexity suggested by computation trees, namely, the number of nodes called by recursion and the maximal number of AND/OR alternations on a branch. Both measures are shown to collapse, or more precisely, it is shown how every logic program can be transformed to a program computing the same function of which the computation tree has at most one called node and at most two alternations on every branch. Some conclusions related to this Normal Form Theorem are discussed. Theoretical results with the attempts to develop a practical methodology for the construction of logic programs are compared.     

Learning higher-order logic programs

Machine Learning - A key feature of inductive logic programming is its ability to learn first-order programs, which are intrinsically more expressive than propositional programs. In this paper, we...     

On computing logic programs

In this paper we present and compare some classical problem-solving methods for computing the stable models of logic programs with negation. Using a graph theoretic representation of logic programs and their stable models, we discuss and compare linear programming, propositional satisfiability, constraint satisfaction, and graph methods.     

Proving pointer programs in higher-order logic

Building on the work of Burstall, this paper develops sound modelling and reasoning methods for imperative programs with pointers: heaps are modelled as mappings from addresses to values, and pointer structures are mapped to higher-level data types for verification. The programming language is embedded in higher-order logic. Its Hoare logic is derived. The whole development is purely definitional and thus sound. Apart from some smaller examples, the viability of this approach is demonstrated with a non-trivial case study. We show the correctness of the Schorr–Waite graph marking algorithm and present part of its readable proof in Isabelle/HOL.     

Detection of And-Parallelism in Logic Programs

In this paper,we present a detection technique of and-parallelism in logic programs.The detection consists of three phases:analysis of entry modes,derivation of exit modes and determination of execution graph expressions.Compared with other techniques^[2,4,5],our approach with the compile-time program-level data-dependence analysis of logic programs,can efficiently exploit and-parallelism in logic programs.Two precompilers,based on our technique and DeGroot‘s approach^[3] respectively,have been implemented in SES-PIM system^[12],Through compiling and running some typical benchmarks in SES-PIM,we conclude that our technique can,in most cases,exploit as much and-parallelism as the dynamic approach^[13]does under“produces-consumer”scheme,and needs less dynamic overhead while exploiting more and parallelism than DeGroot‘s approach does.     

Grammar-related transformations of logic programs

We investigate a simple transformation of logic programs capable of inverting the order of computation. Several examples are given which illustrate how this transformation may serve such purposes as left-recursion elimination, loop-elimination, simulation of forward reasoning, isotopic modification of programs and simulation of abductive reasoning.     

On computability by logic programs

The problem of computational completeness of Horn clause logic programs is revisited. The standard results on representability of all computable predicates by Horn clause logic programs are not related to the real universe on which logic programs operate. SLD-resolution, which is the main mechanism to execute logic programs, may give answer substitutions with variables. As the main result we prove that computability by Horn clause logic programs is equivalent to standard computability over the Herbrand universe with variables. The semantics we use isS-semantics introduced by Falaschi et al. [3]. As an application of the main result we prove the existence of a metainterpreter for a sublanguage of real Prolog, written in the language of Horn clauses with the S-semantics. We also show that the traditional semantics of Prolog do not reflect its computational behavior from the viewpoint of recursion theory.This article is a revised version of [13]. The work was essentially done during author's visit to ECRC.     

Learning hierarchical probabilistic logic programs

Machine Learning - Probabilistic logic programming (PLP) combines logic programs and probabilities. Due to its expressiveness and simplicity, it has been considered as a powerful tool for learning...     

Linearizing some recursive logic programs

We give a sufficient condition under which the least fixpoint of the equation X=a+f(X)X equals the least fixpoint of the equation X=a+f(a)X. We then apply that condition to recursive logic programs containing chain rules: we translate it into a sufficient condition under which a recursive logic program containing n⩾2 recursive calls in the bodies of the rules is equivalent to a linear program containing at most one recursive call in the bodies of the rules. We conclude with a discussion comparing our condition with the other approaches to linearization studied in the literature     

Rule-based coordination of logic programs

Shared Prolog (SP) is a parallel symbolic language in which coordination issues are clearly separated from computation issues. SP combines concurrency and communication based on a shared dataspace coordination model with sequential symbolic computation based on logic programming. We demonstrate how a rule-based coordination language can be used for expressing a number of different parallel computing schemata, reusing and reorganizing existing sequential programs.     

Maintaining distributed logic programs incrementally

Distributed logic programming languages, which allow both facts and programs to be distributed among different nodes in a network, have been recently proposed and used to declaratively program a wide-range of distributed systems, such as network protocols and multi-agent systems. However, the distributed nature of the underlying systems poses serious challenges to developing efficient and correct algorithms for evaluating these programs. This paper proposes an efficient asynchronous algorithm to compute incrementally the changes to the states in response to insertions and deletions of base facts. Our algorithm is formally proven to be correct in the presence of message reordering in the system. To our knowledge, this is the first formal proof of correctness for such an algorithm.