the program composition approach can be fruitfully applied to combine general logic programs, i.e, logic programs possibly containing negative premises. We show how the introduction of a basic set of (meta-level) comp...
详细信息
ISBN:
(纸本)3540632557
the program composition approach can be fruitfully applied to combine general logic programs, i.e, logic programs possibly containing negative premises. We show how the introduction of a basic set of (meta-level) composition operations over general programs increases the knowledge representation capabilities of logicprogramming for non-monotonic reasoning. Examples of modular programming, hierarchical reasoning, constraints, and rules with exceptions will be illustrated. the semantics of programs and program compositions is defined in terms of three-valued logic [15]. the computational interpretation of program compositions is formalised by an equivalence preserving syntactic transformation of arbitrary program compositions into standard general programs.
Although it has been shown that non-monotonic reasoning is presumably harder than classical reasoning, there are cases where a non-monotonic treatment actually simplifies matters. Indeed, one of the reasons for consid...
详细信息
ISBN:
(纸本)3540632557
Although it has been shown that non-monotonic reasoning is presumably harder than classical reasoning, there are cases where a non-monotonic treatment actually simplifies matters. Indeed, one of the reasons for considering non-monotonic systems is the hope of speeding up reasoning, and not to slow it down. In this paper, we consider proof lengths in a cut-free sequent calculus, and we show that the application of circumscription (or completion) to certain first-order formulae leads to a non-elementary speed-up of proof length. this is possible because the introduction of the completion formula can simulate the cut rule.
this paper investigates separated autoepistemic logic which is a generalization of Moore9;s autoepistemic logic with separate modalities for belief and disbelief. Along the separation of beliefs and disbeliefs, the...
详细信息
ISBN:
(纸本)3540632557
this paper investigates separated autoepistemic logic which is a generalization of Moore's autoepistemic logic with separate modalities for belief and disbelief. Along the separation of beliefs and disbeliefs, the relationship between autoepistemic logic and default logic becomes very intuitive. Straightforward ways of translating default theories into separated autoepistemic theories and back are presented. these translations are shown to preserve a variety of semantics of default theories such as those based on default extensions, weak extensions and stationary extensions. these classes of extensions are captured by their analogs in separated autoepistemic logic, and vice versa. A particular novelty of the approach is that a reasonable notion of separated stationary expansions can be established.
We present a bottom-up algorithm for the computation of the well-founded model of non-disjunctive logic programs which is based on the set of elementary program transformations studied by BRASS and DIX [4, 5]. the tra...
详细信息
ISBN:
(纸本)3540632557
We present a bottom-up algorithm for the computation of the well-founded model of non-disjunctive logic programs which is based on the set of elementary program transformations studied by BRASS and DIX [4, 5]. the transformation approach has been introduced in more detail in [7]. In this paper we present a deeper analysis of its complexity and describe an optimized SCC-oriented evaluation. We show that by our method no more work is done than by the alternating fixpoint procedure [23, 24] and that there are examples where our algorithm is significantly superior.
Limiting the number of times a variable appears in either the head or the body of a rule, we identify two classes of normal propositional logic programs. these classes have the desirable property that stable models, i...
详细信息
ISBN:
(纸本)3540632557
Limiting the number of times a variable appears in either the head or the body of a rule, we identify two classes of normal propositional logic programs. these classes have the desirable property that stable models, if they exist, can be found in linear time (worst case). We also identify a related class containing;programs for which the well-founded model can be acquired in linear time, yet for which computing the stable model(s) remains NP-complete. We show in this class how, by relaxing one constraint, previously linear complexity is increased to intractability.
the research on systems of logicprogramming with modules has followed two mainstreams, programming-in-the-large, where compositional operators are provided for combining separate and independent modules, and programm...
详细信息
ISBN:
(纸本)3540632557
the research on systems of logicprogramming with modules has followed two mainstreams, programming-in-the-large, where compositional operators are provided for combining separate and independent modules, and programming-in-the-small, which aims at enhancing logicprogramming with new logical connectives. In this paper, we present a general model theoretic approach to modular logicprogramming which combines programming in-the-large and in-the-small in a satisfactory way. Rather than inventing completely new constructs, however, we resort to a well-known concept in formal logic: generalized quantifiers. We show how generalized quantifiers can be incorporated into logic programs, both for Horn logic programs as well as in the presence of negation. Our basic observation is then that a logic program can be seen as a generalized quantifier, and we obtain a semantics for modular logic programs this way. Generalized quantifiers in logic programs gives rise to interesting classes of logic programs. We present a taxonomy of natural such classes, and investigate their properties. In particular, their expressive power over finite structures is analyzed.
We present an implementation platform for query-answering in default logics. the overall approach along with its implementation, the XRay system, allows for query-answering from default theories supporting local proof...
详细信息
ISBN:
(纸本)3540632557
We present an implementation platform for query-answering in default logics. the overall approach along with its implementation, the XRay system, allows for query-answering from default theories supporting local proof procedures. the deductive power of XRay stems from its usage of Prolog Technology theorem Proving Techniques (PTTP) supported by further enhancements, such as default lemma handling and regularity-based truncations of the underlying search space. the generality of the approach, allowing for a (simultaneous) treatment of different default logics, stems from a novel model-based approach to consistency checking.
Disjunctive Deductive Databases (DDDBs) - function-free disjunctive logic programs with negation in rule bodies allowed - have been recently recognized as a powerful tool for knowledge representation and commonsense r...
详细信息
ISBN:
(纸本)3540632557
Disjunctive Deductive Databases (DDDBs) - function-free disjunctive logic programs with negation in rule bodies allowed - have been recently recognized as a powerful tool for knowledge representation and commonsense reasoning. Much research has been spent on issues like semantics and complexity of DDDBs, but the important area of implementing DDDBs has been less addressed so far. However, a thorough investigation thereof is a basic requirement for building systems which fender previous foundational work on DDDBs useful for practice. this paper presents the architecture of a DDDB system currently developed at TU Vienna in the FWF project P11580-MAT "A Query System for Disjunctive Deductive Databases".
the advantages of FLORID as a deductive object-oriented databaSe system are the rich object-oriented modeling facilities of its language Flogic. the focus of this paper is on FLORID’S multiple inheritance mechanism w...
详细信息
In this paper, we define and investigate the complexity of several nonmonotoniclogics with quantified Boolean formulas as constraints. We give quantified constraint versions of the constraint programming formalism of...
详细信息
暂无评论