检索结果-内蒙古大学图书馆

Embedding defeasible logic into logic programming

theory and practice of logic programming 2006年第0期6卷 703-735页

作者： Antoniou, Grigoris Billington, David Governatori, Guido Maher, Michael J. FORTH Inst Comp Sci Iraklion Greece Griffith Univ Sch ICT Nathan Qld 4111 Australia Univ Queensland Sch ITEE St Lucia Qld 4067 Australia UNSW Natl ICT Australia Kensington NSW Australia

Defeasible reasoning is a simple but efficient approach to nonmonotonic reasoning that has recently attracted considerable interest and that has found various applications. Defeasible logic and its variants are an important family of defeasible reasoning methods. So far no relationship has been established between defeasible logic and mainstream nonmonotonic reasoning approaches. In this paper we establish close links to known semantics of logic programs. In particular, we give a translation of a defeasible theory D into a meta-program P(D). We show that under a condition of decisiveness, the defeasible consequences of D correspond exactly to the sceptical conclusions of P(D) under the stable model semantics. Without decisiveness, the result holds only in one direction (all defeasible consequences of D are included in all stable models of P(D)). If we wish a complete embedding for the general case, we need to use the Kunen semantics of P(D), instead.

关键词： defeasible logic stable semantics Kunen semantics non-monotonic logic

来源：评论

学校读者我要写书评

暂无评论

Stabilization of cooperative information agents in unpredictable environment: a logic programming approach

引用

theory and practice of logic programming 2006年第0期6卷 1-22页

作者： Dung, PM Hanh, DD Thang, PM Asian Inst Technol Comp Sci & Informat Management Dept Bangkok Thailand

An information agent is viewed as a deductive database consisting of three parts: (.) an observation database containing the facts the agent has observed or sensed from its surrounding environment;(.) an input database containing the information the agent has obtained from other agents;(.) an intensional database which is a set of rules for computing derived information from the information stored in the observation and input databases. Stabilization of a system of information agents represents a capability of the agents to eventually get correct information about their Surrounding despite unpredictable environment changes and the incapability of many agents to sense Such changes causing them to have temporary incorrect information. We argue that the stabilization of a system of cooperative information agents could be understood as the convergence of the behavior of the whole system toward the behavior of a "superagent", who has the sensing and Computing capabilities of all agents combined. We show that unfortunately, stabilization is not guaranteed in general, even if the agents are fully cooperative and do not hide any information from each other. We give sufficient conditions for stabilization. We discuss the consequences of our results.

关键词： stabilization cooperative information agents logic programming

来源：评论

学校读者我要写书评

暂无评论

Graphs and colorings for answer set programming

引用

theory and practice of logic programming 2006年第1-2期6卷 61-106页

作者： Konczak, K Linke, T Schaub, T Univ Potsdam Inst Informat D-14439 Potsdam Germany Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

We investigate the usage of rule dependency graphs and their colorings for characterizing and computing answer sets of logic programs. This approach provides us with insights into the interplay between rules when inducing answer sets. We start with different characterizations of answer sets in terms of totally colored dependency graphs that differ ill graph-theoretical aspects. We then develop a series of operational characterizations of answer sets in terms of operators on partial colorings. In analogy to the notion of a derivation in proof theory, our operational characterizations are expressed as (non-deterministically formed) sequences of colorings, turning an uncolored graph into a totally colored one. In this way, we obtain an operational framework in which different combinations of operators result in different formal properties. Among others, we identify the basic strategy employed by the noMoRe system and justify its algorithmic approach. Furthermore, we distinguish operations corresponding to Fitting's operator as well as to well-founded semantics.

关键词： answer set programming operational semantics answer set computation graph-based characterization

来源：评论

学校读者我要写书评

暂无评论

Preferred answer sets for ordered logic programs

引用

theory and practice of logic programming 2006年第1-2期6卷 107-167页

作者： Van Nieuwenborgh, D Vermeir, D Vrije Univ Brussel Dept Comp Sci B-1050 Brussels Belgium

We extend answer set semantics to deal with inconsistent programs (containing classical negation), by finding a "best" answer set. Within the context of inconsistent programs, it is natural to have a partial order on rules, representing a preference for satisfying certain rules, possibly at the cost of violating less important ones. We show that such a rule order induces a natural order on extended answer sets, the minimal elements of which we call preferred answer sets. We characterize the expressiveness of the resulting semantics and show that it can simulate negation as failure, disjunction and some other formalisms such as logic programs with ordered disjunction. The approach is shown to be useful in several application areas, e.g. repairing database, where minimal repairs correspond to preferred answer sets.

关键词： nonmonotonic reasoning knowledge representation answer set programming preference

来源：评论

学校读者我要写书评

暂无评论

Epistemic foundation of stable model semantics

引用

theory and practice of logic programming 2006年第4期6卷 355-393页

作者： Loyer, Yann Straccia, Umberto Univ Versailles Lab PRiSM F-78000 Versailles France CNR Ist Sci & Tecnol Informaz A Faedo Pisa Italy

Stable model semantics has become a very popular approach for the management of negation in logic programming. This approach relies mainly on the closed world assumption to complete the available knowledge and its formulation has its basis in the so-called Gelfond-Lifschitz transformation. The primary goal of this work is to present an alternative and epistemic-based characterization of stable model semantics, to the Gelfond-Lifschitz transformation. In particular, we show that stable model semantics can be defined entirely as an extension of the Kripke-Kleene semantics. Indeed, we show that the closed world assumption can be seen as an additional source of 'falsehood' to be added cumulatively to the Kripke-Kleene semantics. Our approach is purely algebraic and can abstract from the particular formalism of choice as it is based on monotone operators (under the knowledge order) over bilattices only.

关键词： bilattices fixed-point semantics logic programs stable model semantics non-monotonic reasoning

来源：评论

学校读者我要写书评

暂无评论

Towards automated integration of guess and check programs in answer set programming: a meta-interpreter and applications

引用

theory and practice of logic programming 2006年第0期6卷 23-60页

作者： Eiter, T Polleres, A Tech Univ Inst Informat Syst Arbeitsbereich Wissensbasierte Syst Vienna Austria Univ Innsbruck Inst Informat DERI A-6020 Innsbruck Austria

Answer set programming (ASP) with disjunction offers a powerful tool for declaratively representing and solving hard problems. Many NP-complete problems can be encoded ill the answer set semantics of logic programs in a very concise and intuitive way, where the encoding reflects the typical "guess and check" nature of NP problems: The property is encoded in a way such that polynomial size certificates for it correspond to stable models ofa program. However, the problem-solving capacity of full disjunctional logic programs (DI-Ps) is beyond NP, and captures a class of problems at the second level of the polynomial hierarchy. While these problems also have a clear "guess and check" structure, finding an encoding in a DLP reflecting this structure may sometimes be a non-obvious task, in particular if the "check" itself is a co-NP-cornplete problem;usually, Such problems are solved by interleaving separate guess and check programs, where the check is expressed by inconsistency of the check program. In this paper, we present general transformations of head-cycle free (extended) disjunctive logic programs into stratified and positive (extended) disjunctive logic programs based oil meta-interpretation techniques. The answer sets of the original and the transformed program are in simple correspondence, and, moreover, inconsistency of the original program is indicated by a designated answer set of the transformed program. Our transformations facilitate the integration of separate "guess" and "check" programs, which are often easy to obtain, automatically into a single disjunctive logic program. Our results complement recent results on meta-interpretation in ASP, and extend methods and techniques for a declarative "guess and check" problem solving paradigm through ASP.

关键词： answer set programming disjunctive logic programs guess and check paradigm meta-interpretation automated program synthesis

来源：评论

学校读者我要写书评

暂无评论

programming finite-domain constraint propagators in action rules

引用

theory and practice of logic programming 2006年第5期6卷 483-507页

作者： Zhou, Neng-Fa CUNY Brooklyn Coll Dept Comp & Informat Sci Brooklyn NY 11210 USA CUNY Grad Ctr New York NY USA

In this paper, we propose a new language, called AR (Action Rules), and describe how various propagators for finite-domain constraints can be implemented in it. An action rule specifies a pattern for agents, an action that the agents can carry out, and an event pattern for events that can activate the agents. AR combines the goal-oriented execution model of logic programming with the event-driven execution model. This hybrid execution model facilitates programming constraint propagators. A propagator for a constraint is an agent that maintains the consistency of the constraint and is activated by the updates of the domain variables in the constraint. AR has a much stronger descriptive power than indexicals, the language widely used in the current finite-domain constraint systems, and is flexible for implementing not only interval-consistency but also arc-consistency algorithms. As examples, we present a weak arc-consistency propagator for the all-distinct constraint and a hybrid algorithm for n-ary linear equality constraints. B-Prolog has been extended to accommodate action rules. Benchmarking shows that B-Prolog as a CLP(FD) system significantly outperforms other CLP(FD) systems.

关键词： constraint programming constraint propagation action rules

来源：评论

学校读者我要写书评

暂无评论

On the existence of stable models of non-stratified logic programs

引用

theory and practice of logic programming 2006年第0期6卷 169-212页

作者： Costantini, S Univ Aquila Dipartimento Informat I-67010 Coppito Italy

In this paper we analyze the relationship between cyclic definitions and consistency in Gelfond-Lifschitz's answer sets semantics (originally defined as 'stable model semantics'). This paper introduces a fundamental result, which is relevant for Answer Set programming, and planning. For the first time since the definition of the stable model semantics, the class of logic programs for which a stable model exists is given a syntactic characterization. This condition may have a practical importance both for defining new algorithms for checking consistency and computing answer sets, and for improving the existing systems. The approach of this paper is to introduce a new canonical form (to which any logic program can be reduced to), to focus the attention on cyclic dependencies. The technical result is then given in terms of programs in canonical form (canonical programs), without loss of generality: the stable models of any general logic program coincide (up to the language) to those of the corresponding canonical program. The result is based on identifying the cycles contained in the program, showing that stable models of the overall program are composed of stable models of suitable sub-programs, corresponding to the cycles, and on defining the Cycle Graph. Each vertex of this graph corresponds to one cycle, and each edge corresponds to one handle, which is a literal containing an atom that, occurring in both cycles, actually determines a connection between them. In fact, the truth value of the handle in the cycle where it appears as the head of a rule, influences the truth value of the atoms of the cycle(s) where it occurs in the body. We can therefore introduce the concept of a handle path, connecting different cycles. Cycles can be even, if they consist of an even number of rules, or vice versa they call be odd. Problems for consistency, as it is well-known, originate in the odd cycles. If for every odd cycle we can find a handle path with certain properties, then t

关键词： answer set semantics logic programs class canonical programs

来源：评论

学校读者我要写书评

暂无评论

A three-valued semantics for logic programmers

引用

theory and practice of logic programming 2006年第0期6卷 509-538页

作者： Naish, Lee Univ Melbourne Dept Comp Sci & Software Engn Melbourne Vic 3010 Australia

This paper describes a simpler way for programmers to reason about the correctness of their code. The study of semantics of logic programs has shown strong links between the model theoretic semantics (truth and falsity of atoms in the programmer's interpretation of a program), procedural semantics (for example, SLD resolution) and fixpoint semantics (which is useful for program analysis and alternative execution mechanisms). Most of this work assumes that intended interpretations are two-valued: a ground atom is true (and should succeed according to the procedural semantics) or false (and should not succeed). In reality, intended interpretations are less precise. Programmers consider that some atoms "should not occur" or are "ill-typed" or "inadmissible". Programmers don't know and don't care whether such atoms succeed. In this paper we propose a three-valued semantics for (essentially) pure Prolog programs with (ground) negation as failure which reflects this. The semantics of Fitting is similar but only associates the third truth value with non-termination. We provide tools to reason about correctness of programs without the need for unnatural precision or undue restrictions on programming style. As well as theoretical results, we provide a programmer-oriented synopsis. This work has come out of work on declarative debugging, where it has been recognised that inadmissible calls are important.

关键词： models immediate consequence operator SLDNF resolution negation verification declarative debugging inadmissibility

来源：评论

学校读者我要写书评

暂无评论

Improving PARMA trailing

引用

theory and practice of logic programming 2006年第0期6卷 609-644页

作者： Schrijvers, Tom Demoen, Bart De la Banda, Maria Garcia Stuckey, Peter J. Katholieke Univ Leuven Dept Comp Sci Louvain Belgium Monash Univ Sch Comp Sci & Software Engn Clayton Vic 3168 Australia Univ Melbourne Dept Comp Sci & Software Engn NICTA Victoria Lab Parkville Vic 3052 Australia

Taylor introduced a variable binding scheme for logic variables in his PARMA system, that uses cycles of bindings rather than the linear chains of bindings used in the standard WAM representation. Both the HAL and dProlog languages make use of the PARMA representation in their Herbrand constraint solvers. Unfortunately, PARMA's trailing scheme is considerably more expensive in both time and space consumption. The aim of this paper is to present several techniques that lower the cost. First, we introduce a trailing analysis for HAL using the classic PARMA trailing scheme that detects and eliminates unnecessary trailings. The analysis, whose accuracy comes from HAL's determinism and mode declarations, has been integrated in the HAL compiler and is shown to produce space improvements as well as speed improvements. Second, we explain how to modify the classic PARMA trailing scheme to halve its trailing cost. This technique is illustrated and evaluated both in the context of dProlog and HAL. Finally, we explain the modifications needed by the trailing analysis in order to be combined with our modified PARMA trailing scheme. Empirical evidence shows that the combination is more effective than any of the techniques when used in isolation.

关键词： constraint logic programming program analysis trailing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：