We present a heuristic framework for attacking the undecidable termination problem of logic programs, as an alternative to current termination/nontermination proof approaches. We introduce an idea of termination predi...
详细信息
We present a heuristic framework for attacking the undecidable termination problem of logic programs, as an alternative to current termination/nontermination proof approaches. We introduce an idea of termination prediction, which predicts termination of a logic program in case that neither a termination nor a non-termination proof is applicable. We establish a necessary and sufficient characterization of infinite (generalized) SLDNF-derivations with arbitrary (concrete or moded) queries, and develop an algorithm that predicts termination of general logic programs with arbitrary nonfloundering queries. We have implemented a termination prediction tool and obtained quite satisfactory experimental results. Except for five programs which break the experiment time limit, Our prediction is 100% correct for all 296 benchmark programs of the Termination Competition 2007, of which 18 programs cannot be proved by any of the existing state-of-the-art analyzers like AProVE07, NTI, Polytool, and TALP.
This paper develops a declarative language, P-log, that combines logical and probabilistic arguments in its reasoning. Answer Set Prolog is used as the logical foundation, while causal Bayes nets serve as a probabilis...
详细信息
This paper develops a declarative language, P-log, that combines logical and probabilistic arguments in its reasoning. Answer Set Prolog is used as the logical foundation, while causal Bayes nets serve as a probabilistic foundation. We give several non-trivial examples and illustrate the use of P-log for knowledge representation and updating of knowledge. We argue that Our approach to updates is more appealing than existing approaches. We give sufficiency conditions for the coherency of P-log programs and show that Bayes nets can be easily mapped to coherent P-log programs.
Realizability theory is not just a fundamental tool in logic and computability. It also has direct application to the design and implementation of programs, since it can produce code interfaces for the data structure ...
详细信息
Realizability theory is not just a fundamental tool in logic and computability. It also has direct application to the design and implementation of programs, since it can produce code interfaces for the data structure corresponding to a mathematical theory. Our tool, called RZ, serves as a bridge between the worlds of constructive mathematics and programming. By using the realizability interpretation of constructive mathematics, RZ translates specifications in constructive logic into annotated interface code in Objective Caml. The system supports a rich input language allowing descriptions of complex mathematical structures. RZ does not extract code from proofs, but allows any implementation method, from handwritten code to code extracted from proofs by other tools.
Traditional algorithms for description logic (DL) instance retrieval are inefficient for large amounts of underlying data. As DL is becoming more and more Popular in areas Such as the Semantic Web and information inte...
详细信息
Traditional algorithms for description logic (DL) instance retrieval are inefficient for large amounts of underlying data. As DL is becoming more and more Popular in areas Such as the Semantic Web and information integration, it is very important to have systems which can reason efficiently over large data sets. In this paper we present all approach to transform DL axioms, formalised in the SHIQ DL language, into a Prolog program under the unique name assumption. This transformation is performed with no knowledge about particular individuals: they are accessed dynamically during the normal Prolog execution of the generated program. This technique, together with the top-down Prolog execution, implies that only those pieces of data are accessed that are indeed important for answering the query. This makes it possible to store the individuals in a database instead of memory, which results in better scalability and helps in using DL ontologies directly on top of existing information sources. The transformation process consists of two steps: (1) the DL axioms are converted to first-order clauses of a restricted form, and (2) a Prolog program is generated from these clauses. Step (2), which is the focus of the present paper, actually works on more general clauses than those obtainable by applying step (1) to a SHIQ knowledge base. We first present a base transformation, the Output of which can be either executed Using a simple interpreter or further extended to executable Prolog code. We then discuss several optimisation techniques, applicable to the output of the base transformation. Some of these techniques are specific to our approach, while others are general enough to be interesting for DL reasoner implementors not using Prolog. We give ail overview of DLog, a DL reasoner in Prolog, which is an implementation of the techniques outlined above. We evaluate the performance of DLog and compare it to some widely used DL reasoners, such as RacerPro, Pellet and KAON2.
Disjunctive finitary programs are a class of logic programs admitting function symbols and hence infinite domains. They have very good computational properties;for example, ground queries are decidable, while in the g...
详细信息
Disjunctive finitary programs are a class of logic programs admitting function symbols and hence infinite domains. They have very good computational properties;for example, ground queries are decidable, while in the general case the stable model semantics are Pi(1)(1)-hard. In this paper we prove that a larger class of programs, called finitely recursive programs, preserve most of the good properties of finitary programs under the stable model semantics, which are as follows: (i) finitely recursive programs enjoy a compactness property;(ii) inconsistency checking and skeptical reasoning are semidecidable;(iii) skeptical resolution is complete for normal finitely recursive programs. Moreover, we show how to check inconsistency and answer skeptical queries using finite subsets of the ground program instantiation. We achieve this by extending the splitting sequence theorem by Lifschitz and Turner: we prove that if the input program P is finitely recursive, then the partial stable models determined by any smooth splitting omega-sequence converge to a stable model of P.
Equilibrium logic is an approach to non-monotonic reasoning that extends the stable-model and answer-set semantics for logic programs. In particular, it includes the general case of nested logic programs, where arbitr...
详细信息
Equilibrium logic is an approach to non-monotonic reasoning that extends the stable-model and answer-set semantics for logic programs. In particular, it includes the general case of nested logic programs, where arbitrary Boolean combinations are permitted in heads and bodies of rules, as special kinds of theories. In this paper, we present polynomial reductions Of the main reasoning tasks associated with equilibrium logic and nested logic programs into quantified propositional logic, an extension of classical propositional logic where quantifications over atomic formulas are permitted. Thus, quantified propositional logic is a fragment of second-order logic, and its formulas are usually referred to as quantified Boolean formulas (QBFs). We provide reductions not only for decision problems, but also for the central semantical concepts of equilibrium logic and nested logic programs. In particular, our encodings map a given decision problem into some QBF such that the latter is valid precisely in case the former holds. The basic tasks we deal with here are the consistency, problem, brave reasoning and skeptical reasoning. Additionally, we also provide encodings for testing equivalence of theories or programs under different notions of equivalence, viz. ordinary, strong and uniform equivalence. For all considered reasoning tasks, we analyse their computational complexity and give strict complexity bounds. Hereby, our encodings yield upper bounds in a direct manner Besides this useful feature, our approach has the following benefits: First, Our encodings yield a uniform axiomatisation for a variety of problems in a common language. Second, extant solvers for QBFs can be used as back-end inference engines to realise implementations of the encoded task in a rapid prototyping manner. Third, our axiomatisations also allow us to straightforwardly relate equilibrium logic with circumscription.
This paper presents a computational model for the cooperation of constraint domains and an implementation for a particular case of practical importance. The computational model supports declarative programming with la...
详细信息
This paper presents a computational model for the cooperation of constraint domains and an implementation for a particular case of practical importance. The computational model supports declarative programming with lazy and possibly higher-order functions, predicates, and the cooperation of different constraint domains equipped with their respective solvers, relying on a so-called constraint functional logicprogramming (CFLP) scheme. The implementation has been developed on top of the CFLP system FOY, supporting the cooperation of the three domains H, R, and FD, which supply equality and disequality constraints over symbolic terms, arithmetic constraints over the real numbers, and finite domain constraints over the integers, respectively. The computational model has been proved sound and complete w.r.t. the declarative semantics provided by the CFLP scheme, while the implemented system has been tested with a set of benchmarks and shown to behave quite efficiently in comparison to the closest related approach we are aware of.
This paper studies the stable model semantics of logic programs with (abstract) constraint,items and their properties. We introduce a succinet abstract representation of these constraint atoms in which a constraint at...
详细信息
This paper studies the stable model semantics of logic programs with (abstract) constraint,items and their properties. We introduce a succinet abstract representation of these constraint atoms in which a constraint atom is represented compactly. We show two applications. First, under this representation of constraint atoms, we generalize the Gelfond-Litschitz transformation and apply it to define stable models (also called answer sets) for logic programs with arbitrary constraint atoms. The resulting semantics turns Out to coincide with the one defined by Son et al. (2007), which is based oil a fixpoint approach. One advantage of our approach is that it can be applied, in a natural way, to define stable models for disjunctive logic programs with constraint atoms, which may appear in the disjunctive head as well as in the body of a rule. As a result, Our approach to the stable model semantics for logic programs with constraint atoms generalizes a number of previous approaches. Second, we show that our abstract representation of constraint atoms provides a means to characterize dependencies of atoms in it program with constraint atoms, so that some standard characterizations and properties relying on these dependencies in the past for logic programs with ordinary atoms can be extended to logic programs with constraint atoms.
Realizability theory is not just a fundamental tool in logic and computability. It also has direct application to the design and implementation of programs, since it can produce code interfaces for the data structure ...
详细信息
ISBN:
(纸本)9783540730002
Realizability theory is not just a fundamental tool in logic and computability. It also has direct application to the design and implementation of programs, since it can produce code interfaces for the data structure corresponding to a mathematical theory. Our tool, called RZ, serves as a bridge between the worlds of constructive mathematics and programming. By using the realizability interpretation of constructive mathematics, RZ translates specifications in constructive logic into annotated interface code in Objective Caml. The system supports a rich input language allowing descriptions of complex mathematical structures. RZ does not extract code from proofs, but allows any implementation method, from handwritten code to code extracted from proofs by other tools.
暂无评论