Distributed reasoning with ontologies and rules in order-sorted logic programming

Integrating ontologies and rules on the Semantic Web enables software agents to interoperate between them; however, this leads to two problems. First, reasoning services in SWRL (a combination of OWL and RuleML) are not decidable. Second, no studies have focused on distributed reasoning services for integrating ontologies and rules in multiple knowledge bases. In order to address these problems, we consider distributed reasoning services for ontologies and rules with decidable and effective computation. In this paper, we describe multiple order-sorted logic programming that transfers rigid properties from knowledge bases. Our order-sorted logic contains types (rigid sorts), non-rigid sorts, and unary predicates that distinctly express essential sorts, non-essential sorts, and non-sortal properties. We formalize the order-sorted Horn-clause calculus for such properties in a single knowledge base. This calculus is extended by embedding rigid-property derivation for multiple knowledge bases, each of which can transfer rigid-property information from other knowledge bases. In order to enable the reasoning to be effective and decidable, we design a query-answering system that combines order-sorted linear resolution and rigid-property resolution as top-down algorithms.     

Beyond multi-adjoint logic programming

In ‘multi-adjoint logic programming’, MALP in brief, each fuzzy logic program is associated with its own ‘multi-adjoint lattice’ for modelling truth degrees beyond the simpler case of true and false, where a large set of fuzzy connectives can be defined. On this wide repertoire, it is crucial to connect each implication symbol with a proper conjunction thus conforming constructs of the form (←_i, &_i) called ‘adjoint pairs’, whose use directly affects both declarative and operational semantics of the MALP framework. In this work, we firstly show how the strong dependence of adjoint pairs can be largely weakened for an interesting ‘sub-class’ of MALP programs. Then, we reason in a similar way till conceiving a ‘super-class’ of fuzzy logic programs beyond MALP, which definitively drops out the need for using adjoint pairs, since the new semantics behaviour relies on much more relaxed lattices than multi-adjoint ones.     

Relevant logic programming

In this paper we present a fragment of (positive) relevant logic which can be computed by a straightforward extension to SLD resolution while allowing full nesting of implications. These two requirements lead quite naturally to a fragment in which the major feature is an ambiguous user-level conjunction which is interpreted intensionally in query positions and extensionally in assertion positions. These restrictions allow a simple and efficient extension to SLD resolution (and more particularly, the PROLOG evaluation scheme) with quite minor loss in expressive power.     

DISLOG: programming in logic with discontinuities

In this paper, we present an extension to PROLOG we call DISLOG which is designed to deal with relations between non-contiguous elements in a structure. This extension turns out to be well suited for syntactic analysis of natural and artificial languages. It is also well adapted to express traversal constraints in applications such as planning and expert systems and deductive systems involving, for example, temporal reasoning, DISLOG belongs to the constrained logic programming paradigm and turns out to be more declarative, transparent, and simple than PROLOG to deal with longdistance relations.     

Tableaux for logic programming

We present a logic programming language, which we call Proflog, with an operational semantics based on tableaux and a denotational semantics based on supervaluations. We show the two agree. Negation is well behaved, and semantic noncomputability issues do not arise. This is accomplished essentially by dropping a domain closure requirement. The cost is that intuitions developed through the use of classical logic may need modification, though the system is still classical at a level once removed. Implementation problems are discussed very briefly; the thrust of the paper is primarily theoretical.Research partly supported by NSF Grant CCR-9104015.     

A decidable first-order logic for knowledge representation

Decidable first-order logics with reasonable model-theoretic semantics have several benefits for knowledge representation. These logics have the expressive power of standard first order logic along with an inference algorithm that will always terminate, both important considerations for knowledge representation. Knowledge representation systems that include a faithful implementation of one of these logics can also use its model-theoretic semantics to provide meanings for the data they store. One such logic, a variant of a simple type of first-order relevance logic, is developed and its properties described. This logic, although extremely weak, does capture a non-trivial and well-motivated set of inferences that can be entrusted to a knowledge representation system.This is a revised and much extended version of a paper of the same name that appears in the Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, California, 1985.     

A logic programming system for nonmonotonic reasoning

The evolution of logic programming semantics has included the introduction of a new explicit form of negation, beside the older implicit (or default) negation typical of logic programming. The richer language has been shown adequate for a spate of knowledge representation and reasoning forms.The widespread use of such extended programs requires the definition of a correct top-down querying mechanism, much as for Prolog wrt. normal programs. One purpose of this paper is to present and exploit a SLDNF-like derivation procedure, SLX, for programs with explicit negation under well-founded semantics (WFSX) and prove its soundness and completeness. (Its soundness wrt. the answer-sets semantics is also shown.) Our choice ofWFSX as the base semantics is justi-fied by the structural properties it enjoys, which are paramount for top-down query evaluation.Of course, introducing explicit negation requires dealing with contradiction. Consequently, we allow for contradiction to appear, and show moreover how it can be removed by freely changing the truth-values of some subset of a set of predefined revisable literals. To achieve this, we introduce a paraconsistent version ofWFSX, WFSX _p , that allows contradictions and for which our SLX top-down procedure is proven correct as well.This procedure can be used to detect the existence of pairs of complementary literals inWESX _p simply by detecting the violation of integrity rulesf L, -L introduced for eachL in the language of the program. Furthermore, integrity constraints of a more general form are allowed, whose violation can likewise be detected by SLX.Removal of contradiction or integrity violation is accomplished by a variant of the SLX procedure that collects, in a formula, the alternative combinations of revisable literals' truth-values that ensure the said removal. The formulas, after simplification, can then be satisfied by a number of truth-values changes in the revisable, among true, false, and undefined. A notion of minimal change is defined as well that establishes a closeness relation between a program and its revisions. Forthwith, the changes can be enforced by introducing or deleting program rules for the revisable literals.To illustrate the usefulness and originality of our framework, we applied it to obtain a novel logic programming approach, and results, in declarative debugging and model-based diagnosis problems.     

基于谓词逻辑的设计模式描述方法

设计模式描述了面向对象软件设计过程中不断重复发生的问题以及这些问题的解决方案,强调系统的复用性,帮助人们做出有利于系统复用的选择,因此设计模式也可看成是对软件开发者的分析与设计知识的记录、提炼和表示,谓词逻辑是一种形式语言系统,具有精确、无二义性以及容易为计算机理解和操作等特点.采用了谓词逻辑来形式化描述设计模式,以实现对设计模式精确的形式化描述,并给出了具体的实例分析.     

Non-Horn clause logic programming without contrapositives

We present an extension of Prolog-style Horn clause logic programming to full first order logic. This extension has some advantages over other such extensions that have been proposed. We compare this method with the model elimination strategy which Stickel has recently implemented very efficiently, and with Loveland's extension of Prolog to near-Horn clauses. This new method is based on the author's simplified problem reduction format but permits a better control of the splitting rule than does the simplified problem reduction format. In contrast to model elimination, this new method does not require the use of contrapositives of clauses, permitting a better control of the search. This method has been implemented in C Prolog and has turned out to be a respectable and surprisingly compact first-order theorem prover. This implementation uses depth-first iterative deepening and caching of answers to avoid repeated solution of the same subgoal. We show that the time and space used by this method are polynomial functions of certain natural parameters of the search space, unlike other known methods. We discuss the relation of these upper bounds to Savitch's theorem relating nondeterministic time to deterministic space.This research was supported in part by the National Science Foundation under grant DCR-8516243.     

Defeasible reasoning and logic programming

The general conditions of epistemic defeat are naturally represented through the interplay of two distinct kinds of entailment, deductive and defeasible. Many of the current approaches to modeling defeasible reasoning seek to define defeasible entailment via model-theoretic notions like truth and satisfiability, which, I argue, fails to capture this fundamental distinction between truthpreserving and justification-preserving entailments. I present an alternative account of defeasible entailment and show how logic programming offers a paradigm in which the distinction can be captured, allowing for the modeling of a larger range of types of defeat. This is possible through a natural extension of the declarative and procedural semantics of Horn clauses.     

Multimodal logic programming

We give a framework for developing the least model semantics, fixpoint semantics, and SLD-resolution calculi for logic programs in multimodal logics whose frame restrictions consist of the conditions of seriality (i.e. ) and some classical first-order Horn clauses. Our approach is direct and no special restriction on occurrences of □_i and _i is required. We apply our framework for a large class of basic serial multimodal logics, which are parameterized by an arbitrary combination of generalized versions of axioms T, B, 4, 5 (in the form, e.g. 4:□_i→□_j□_k) and I:□_i→□_j. Another part of the work is devoted to programming in multimodal logics intended for reasoning about multidegree belief, for use in distributed systems of belief, or for reasoning about epistemic states of agents in multiagent systems. For that we also use the framework, and although these latter logics belong to the mentioned class of basic serial multimodal logics, the special SLD-resolution calculi proposed for them are more efficient.     

Semantic forgetting in answer set programming

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.     

Multiple robot programming using a concurrent logic language

Advances in robotics has led to the cooperation of multiple robots among themselves and with their industrial automation environment. Efficient interaction with industrial robots thus becomes one of the key factors in the successful utilization of this modern equipment. When multiple manipulators have to be coordinated, there is a need for a new programming approach that facilitates and encompasses the needs of concurrency, synchronization, timing, and communication. Most robot languages have been developed with little attention being given to the integration of the robot with its environment. Currently, there is a gap between the robot capabilities, the task definition environment, and language facilities supplied to use robots.This paper analyzes the needs and then establishes that a concurrent logic programming approach is a step towards achieving a multi-robot knowledgeable task programming. In particular, the FCP dialect of concurrent Prolog is demonstrated, and analyzed.This research is partially supported by the Paul Ivanier Center for research in robots and production management.     

LMNtal as a hierarchical logic programming language

LMNtal (pronounced “elemental”) is a simple language model based on hierarchical graph rewriting that uses logical variables to represent connectivity and membranes to represent hierarchy. LMNtal is an outcome of the attempt to unify constraint-based concurrency and Constraint Handling Rules (CHR), the two notable extensions to concurrent logic programming. LMNtal is intended to be a substrate language of various computational models, especially those addressing concurrency, mobility and multiset rewriting. Although the principal objective of LMNtal was to provide a unifying computational model, it is of interest to equip the formalism with a precise logical interpretation. In this paper, we show that it is possible to give LMNtal a simple logical interpretation based on intuitionistic linear logic and a flattening technique. This enables us to call LMNtal a hierarchical, concurrent linear logic language.     

Autoepistemic logic programming

An autoepistemic logic programming language is derived from a subset of a three-valued autoepistemic logic, called 3AEL. Autoepistemic programs generalize several ideas underlying logic programming: stable, supported, and well-founded models, Fitting's semantics, Kunen's semantics, and abductive frameworks can all be captured through simple autoepistemic translations; moreover, SLDNF-resolution and a generate-and-test method for stable semantics are generalized to provide sound and complete proof methods for autoepistemic programs. These methods extend existing proof methods for 3AEL. Thus autoepistemic logic programming, besides contributing to the understanding of 3AEL, can be seen as a unifying framework for the theory of logic programs. It should also be regarded as a first step toward a flexible environment where different forms of inference can be formally integrated.This paper is an extended version of [8]. I am grateful to my advisor, Giorgio Levi, to Paolo Mancarella, who read the first version of the paper, and to the anonymous referees, whose comments led to sensible improvements.     

Asynchronous communication model based on linear logic

We propose a new framework called ACL for concurrent computation based on linear logic. ACL is a kind oflinear logic programming framework, where its operational semantics is described in terms ofproof construction in linear logic. We also give a model-theoretic semantics based onphase semantics, a model of linear logic. Our framework well captures concurrent computation based on asynchronous communication. It will, therefore, provide us with a new insight into other models of asynchronous concurrent computation from alogical point of view. We also expect ACL to become a formal framework for analysis, synthesis and transformation of concurrent programs by the use of techniques for traditional logic programming. ACL's attractive features for concurrent programming paradigms are also discussed.     

On the complexity of extension checking in default logic

The complexity of deciding equivalence of a formula to an extension of a default theory is investigated for the Reiter, justified, constrained, and rational semantics.     

Foundations of declarative testing in arbitrary logic programming

Declarative testing is very important in logic program developments, as without testing no one can guarantee that every program is definitely correct, no matter how elegant and high-level the programming languages used. Unfortunately, the activity of declarative testing for logic programs (or even the ordinary testing for conventional programs) has received little attention. There is little formal theory of testing, and attempts to develop a methodology of testing are rare. In this paper, we provide a theoretical foundation for declarative testing in arbitrary first order logic programming using recursion theories. In particular, we present a theoretical analysis of three kinds of declarative testing method: I/O testing, I/Y testing, and X/Y testing for logic programs.