this paper introduces techniques for updating knowledge bases represented in extended logic programs. three different types of updates, view updates, theory updates, and inconsistency removal, are considered. We formu...
详细信息
ISBN:
(纸本)3540667490
this paper introduces techniques for updating knowledge bases represented in extended logic programs. three different types of updates, view updates, theory updates, and inconsistency removal, are considered. We formulate these updates through abduction, and provide methods for computing them with update programs. An update program is an extended logic program which specifies changes on abductive hypotheses, then updates are computed by the U-minimal answer sets of an update program. the proposed technique provides a uniform framework for these different types of updates, and each update is computed using existing procedures of logicprogramming.
We study the fixed-parameter complexity of various problems in Al and nonmonotonic reasoning. We show that a number of relevant parameterized problems in these areas are fixed-parameter tractable. Among these problems...
详细信息
ISBN:
(纸本)3540667490
We study the fixed-parameter complexity of various problems in Al and nonmonotonic reasoning. We show that a number of relevant parameterized problems in these areas are fixed-parameter tractable. Among these problems are constraint satisfaction problems with bounded treewidth and fixed domain, restricted satisfiability problems, propositional logicprogramming under the stable model semantics where the parameter is the dimension of a feedback vertex set of the program's dependency graph, and circumscriptive inference from a positive k-CNF restricted to models of bounded size. We also show that circumscriptive inference from a general propositional theory, when the attention is restricted to models of bounded size, is fixed-parameter intractable and is actually complete for a novel fixed-parameter complexity class.
dlv is a knowledge representation system, based on disjunctive logicprogramming, which offers front-ends to several advanced KR formalisms. this paper describes new techniques for the computation of answer sets of di...
详细信息
ISBN:
(纸本)3540667490
dlv is a knowledge representation system, based on disjunctive logicprogramming, which offers front-ends to several advanced KR formalisms. this paper describes new techniques for the computation of answer sets of disjunctive logic programs, that have been developed and implemented in the dlv system. these techniques try to "push" the query goals in the process of model generation (query goals are often present either explicitly, like in planning and diagnosis, or implicitly in the form of integrity constraints). this way, a lot of useless models are discarded "a priori" and the computation converges rapidly toward the generation of the "right" answer set. A few preliminary benchmarks show dramatic efficiency gains due to the new techniques.
Przymusinski's Autoepistemic logic of Knowledge and Belief (AELKB) is a unifying framework for various non-monotonic formalisms. In this paper we present a semantic characterization of AELKB in terms of Dynamic Kr...
详细信息
ISBN:
(纸本)3540667490
Przymusinski's Autoepistemic logic of Knowledge and Belief (AELKB) is a unifying framework for various non-monotonic formalisms. In this paper we present a semantic characterization of AELKB in terms of Dynamic Kripke Structures (DKS). A DKS is composed of two components - a static one (a Kripke structure) and a dynamic one (a set of transformations). Transformations between possible worlds correspond to hypotheses generation and to revisions. therefore they enable to define a semantics of insertions to and revisions of AELKB-theories. A computation of the transformations (between possible worlds) is based on (an enhanced) model-checking. the transformations may be used as a method of computing static autoepistemic expansions.
this paper reports on systematic research which aims to classify non-monotonic logics by their expressive power. the classification is based on translation functions that satisfy three important criteria: polynomialit...
详细信息
ISBN:
(纸本)3540667490
this paper reports on systematic research which aims to classify non-monotonic logics by their expressive power. the classification is based on translation functions that satisfy three important criteria: polynomiality, faithfulness and modularity (PFM for short). the basic method for classification is to prove that PFM translation functions exist (or do not exist) between certain logics. As a result, non-monotonic logics can be arranged to form a hierarchy. this paper gives an overview of the current expressive power hierarchy (EPH) and investigates semi-normal default logic as well as prerequisite-free and semi-normal default logic in order to locate their exact positions in the hierarchy.
We present many-valued disjunctive logic programs in which classical disjunctive logic program clauses are extended by a truth value that respects the material implication. Interestingly, these many-valued disjunctive...
详细信息
ISBN:
(纸本)3540667490
We present many-valued disjunctive logic programs in which classical disjunctive logic program clauses are extended by a truth value that respects the material implication. Interestingly, these many-valued disjunctive logic programs have both a probabilistic semantics in probabilities over possible worlds and a truth-functional semantics. We then define minimal, perfect, and stable models and show that they have the same properties like their classical counterparts. In particular, perfect and stable models are always minimal models. Under local stratification, the perfect model semantics coincides withthe stable model semantics. Finally, we show that some special cases of propositional many-valued disjunctive logicprogramming under minimal, perfect, and stable model semantics have the same complexity like their classical counterparts.
this paper is concerned with providing a common framework for boththe logical specification and execution of agents. While numerous high-level agent theories have been proposed in order to model agents, such as theor...
详细信息
ISBN:
(纸本)1558606130
this paper is concerned with providing a common framework for boththe logical specification and execution of agents. While numerous high-level agent theories have been proposed in order to model agents, such as theories of intention, these often have little formal connection to practical agent-based systems. On the other hand, many of the agent-based programming languages used for implementing 'real' agents lack firm logical semantics. Our approach is to define a logical framework in which agents can be specified, and then show how such specifications can be directly executed in order to implement the agent's behaviour. We here extend this approach to capture an important aspect of practical agents, namely their resource-bounded nature. We present a logic in which resource-boundedness can be specified, and then consider how specifications within this logic can be directly executed. the mechanism we use to capture finite resources is to replace the standard modal logic previously used to represent an agent's beliefs, with a multi-context representation of belief, thus providing tight control over the agent's reasoning capabilities where necessary. this logical framework provides the basis for the specification and execution of agents comprising dynamic (temporal) activity, deliberation concerning goals, and resource-bounded reasoning.
In this paper, we propose a new semantics for disjunctive logicprogramming and deductive databases. the semantics, called minimal founded, generalizes stable model semantics for normal (i.e. non disjunctive) programs...
详细信息
ISBN:
(纸本)3540667490
In this paper, we propose a new semantics for disjunctive logicprogramming and deductive databases. the semantics, called minimal founded, generalizes stable model semantics for normal (i.e. non disjunctive) programs but differs from disjunctive stable model semantics (the extension of stable model semantics for disjunctive programs). Compared with disjunctive stable model semantics, the minimal founded semantics seems to be, in some case, more intuitive, it gives meaning to programs which are meaningless under stable model semantics and it is not harder to compute. We study the expressive power of the semantics and show that for general disjunctive datalog programs it has the same power of disjunctive stable model semantics. We also present a variation of the minimal founded semantics, called strongly founded which on stratified programs coincide withthe perfect model semantics.
Extended logic programs and annotated logic programs are two important extensions of normal logic programs that allow for a more concise and declarative representation of knowledge. Extended logic programs add explici...
详细信息
ISBN:
(纸本)3540667490
Extended logic programs and annotated logic programs are two important extensions of normal logic programs that allow for a more concise and declarative representation of knowledge. Extended logic programs add explicit negation to the default negation of normal programs in order to distinguish what can be shown to be false from what cannot be proven true. Annotated logic programs generalize the set of truth values over which a program is interpreted by explicitly annotating atoms with elements of a new domain of truth values. In this paper coherent well-founded annotated programs are defined, and shown to generalize both consistent and paraconsistent extended programs, along with several classes of annotated programs.
In this paper, we shall provide a translation of a class of causal theories in (Lin [3]) to Gelfond and Lifschitz's disjunctive logic programs with classical negation [1]. We found this translation interesting for...
详细信息
ISBN:
(纸本)3540667490
In this paper, we shall provide a translation of a class of causal theories in (Lin [3]) to Gelfond and Lifschitz's disjunctive logic programs with classical negation [1]. We found this translation interesting for at least the following two reasons: it provides a basis on which a wide class of causal theories in ([3]) can be computed;and it sheds some new lights on the nature of the causal theories in [3]. Our translation is in many ways similar to the one given in [9,2]. Our main result is a theorem that shows how action precondition and fully instantiated successor state axioms can be computed from the answer sets of the translated logic program.
暂无评论