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

The diagnosis frontend of the dlv system

AI COMMUNICATIONS 1999年第1-2期12卷 99-111页

作者： Eiter, T Faber, W Leone, N Pfeifer, G Vienna Tech Univ Inst Informat Syst A-1040 Vienna Austria

This paper presents the Diagnosis Frontend of dlv, which is a knowledge representation system under development at the Technische Universitat Wien. The kernel language of the system is an extension of disjunctive logic programming (DLP) by integrity constraints;it offers frontends to several advanced knowledge representation formalisms. The formal model of diagnosis employed in the frontend includes both abductive diagnosis (over DLP theories) and consistency-based diagnosis. For each of the two diagnosis modalities, generic diagnoses, single error diagnoses, and subset minimal diagnoses are considered. We illustrate the use of the frontend by showing the dlv encodings of several diagnosis problems. Thereafter, we discuss implementation issues. Diagnostic reasoning is implemented on the dlv engine through suitable translations of diagnostic problems into disjunctive logic programs, such that their stable models correspond to diagnoses. For the six kinds of diagnostic reasoning problems emerging from above, such reductions are provided.

关键词： disjunctive logic programming diagnosis abduction stable model

来源：评论

学校读者我要写书评

暂无评论

disjunctive logic programs with inheritance

引用

THEORY AND PRACTICE OF logic programming 2002年第3期2卷 293-321页

作者： Buccafurri, F Faber, W Leone, N Univ Reggio Calabria DIMET I-89100 Reggio Di Calabria Italy Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Univ Calabria Dipartmento Matemat I-87030 Arcavacata Di Rende CS Italy

The paper proposes a new knowledge representation language, called DLP<, which extends disjunctive logic programming (with strong negation) by inheritance. The addition of inheritance enhances the knowledge modeling features of the language providing a natural representation of default reasoning with exceptions. A declarative model-theoretic semantics of DLP< is provided, which is shown to generalize the Answer Set Semantics of disjunctive logic programs. The knowledge modeling features of the language are illustrated by encoding classical nonmonotonic problems in DLP<. The complexity of DLP< is analyzed, proving that inheritance does not cause any computational overhead, as reasoning in DLP< has exactly the same complexity as reasoning in disjunctive logic programming. This is confirmed by the existence of an efficient translation from DLP< to plain disjunctive logic programming. Using this translation, an advanced KR system supporting the DLP< language has been implemented on top of the DLV system and has subsequently been integrated into DLV.

关键词： nonmonotonic reasoning knowledge representation disjunctive logic programming inheritance exceptions

来源：评论

学校读者我要写书评

暂无评论

Expressive power and complexity of partial models for disjunctive deductive databases

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期206卷 181-218页

作者： Eiter, T Leone, N Sacca, D Vienna Univ Technol Dept Informat Syst A-1040 Vienna Austria Univ Giessen Inst Informat D-35392 Giessen Germany Univ Calabria DEIS I-87030 Arcavacata Di Rende Italy

This paper investigates the expressive power and complexity of partial model semantics for disjunctive deductive databases. In particular, partial stable, regular model, maximal stable (M-stable), and least undefined stable (L-stable) semantics for function-free disjunctive logic programs are considered, for which the expressiveness of queries based on possibility and certainty inference is determined. On the complexity side, we determine the data and expression complexity of query evaluation. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of disjunction and negation. It appears that the considered semantics capture complexity classes at the lower end of the polynomial hierarchy. In fact, each class Sigma(i)(P), Pi(i)(P), 1 less than or equal to i less than or equal to 3 is captured by some semantics using appropriate syntactical restrictions. partial stable models have exactly the same expressive power and complexity as total stable models (Sigma(2)(P) resp. Pi(2)(P)), while a higher degree of expressiveness is obtained by the semantics which minimize undefinedness (M-stable, regular, and L-stable semantics). In particular, L-stable semantics has the highest expressive power (Sigma(3)(P) reap. Pi(3)(P)). An interesting result in this course is that, in contrast with total stable models, negation is for partial stable models more expressive than disjunction. For the data complexity of queries, we obtain completeness results for the classes Sigma(i)(P), Pi(i)(P), i less than or equal to 3, and, for the expression complexity, completeness results for the analogous classes at the lower end of the weak exponential hierarchy. The results of this paper complement and extend previous results, and contribute to a more complete picture of the computational aspects of disjunctive logic programming and databases, which supports in choosing an appropriate setting that fits the needs in practice. (C) 1998-E

关键词： deductive databases expressive power complexity disjunctive logic programming partial model semantics

来源：评论

学校读者我要写书评

暂无评论

Bounded treewidth as a key to tractability of knowledge representation and reasoning

引用

ARTIFICIAL INTELLIGENCE 2010年第1期174卷 105-132页

作者： Gottlob, Georg Pichler, Reinhard Wei, Fang Univ Freiburg Inst Informat D-79110 Freiburg Germany Univ Oxford Comp Lab Oxford OX1 3QD England Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria

Several forms of reasoning in Al - like abduction, closed world reasoning, circumscription, and disjunctive logic programming - are well known to be intractable. In fact, many of the relevant problems are on the second or third level of the polynomial hierarchy. in this paper, we show how the notion of treewidth can be fruitfully applied to this area. in particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved formulae or programs is bounded by some constant. Clearly, these theoretical tractability results as such do not immediately yield feasible algorithms. However, we have recently established a new method based on monadic datalog which allowed us to design an efficient algorithm for a related problem in the database area. In this work, we exploit the monadic datalog approach to construct new algorithms for logic-based abduction. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Fixed-parameter tractability Treewidth Monadic datalog Abduction Closed world reasoning disjunctive logic programming

来源：评论

学校读者我要写书评

暂无评论

Optimal models of "disjunctive-logic 'programs: Semantics, complexity, and computation

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2004年第4期16卷 487-503页

作者： Leone, N Scarcello, F Subrahmanian, VS Univ Calabria Dept Math I-87030 Arcavacata Di Rende Italy Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Calabria DEIS I-87030 Arcavacata Di Rende Italy

Almost all semantics for logic programs with negation identify a set, SEM(P), of models of program P, as the intended semantics of P, and any model M in this class is considered a possible meaning of P with regard to the semantics the user has in mind. Thus, for example, in the case of stable models [10], choice models [30], answer sets [11], etc., different possible models correspond to different ways of "completing" the incomplete information in the logic program. However, different end-users may have different ideas Ion which of these different models in SEM(P) is a reasonable one from their point of view. For instance, given SEM(P), user U, may prefer model M-1 is an element of SEM(P) to model M-2 is an element of SEM(P) based on some evaluation criterion that she has. In this paper, we develop a logic program semantics based on Optimal Models. This semantics does not add yet another semantics to the logic programming arena-it takes as input an existing semantics SE-All(P) and a user-specified objective function Obj, and yields a new semantics (Opt) under bar (P) subset of or equal to SEM(P) that realizes the objective function within the framework of preferred models identified already by SEM(P). Thus, the user who may or may not know anything about logic programming has considerable flexibility in making the system reflect her own objectives by building "on top" of,existing semantics known to the system. In addition to the declarative semantics;we provide a complete complexity analysis and algorithms to compute optimal models under varied conditions when SEM(P) is the stable model semantics, the minimal models semantics, and the all-models semantics.

关键词： disjunctive logic programming computational complexity nonmonotonic reasoning knowledge representation optimization problems

来源：评论

学校读者我要写书评

暂无评论

Experimenting with prototype system DLVK via different approach

引用

KNOWLEDGE-BASED SYSTEMS 2006年第8期19卷 681-686页

作者： Shah, Asim Ali Univ Leipzig Inst Comp Sci Dept Intelligent Syst D-04109 Leipzig Germany

Planning allows one to sequence a series of actions to achieve a certain goal. In this paper, we present a short overview of the disjunctive logic programming under the answer set semantics Then we use the proposed DLVK planning system against a well-known blocks world planning domain for fully and partially specified initial state facts and the system performance is checked in the run time CPU seconds while increasing the plan length which are the number of steps presenting the plan quality together with security check feature for each plan to know whether the plan generated is secure. Blocks world planning has been widely investigated by planning researchers, primarily due to its simplicity and also because it captures several of the relevant difficulties that are involved in a typical planning domain. The work presented in this paper contributed mainly as a technique compatible with the extensions and improvements of the existing system rather than as a concrete planning system. (c) 2006 Elsevier B.V. All rights reserved.

关键词： planning DLVK disjunctive logic programming blocks world answer set semantics

来源：评论

学校读者我要写书评

暂无评论

Outlier detection using default reasoning

引用

ARTIFICIAL INTELLIGENCE 2008年第16-17期172卷 1837-1872页

作者： Angiulli, Fabrizio Ben-Eliyahu-Zohary, Rachel Palopoli, Luigi Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Jerusalem Coll Engn Beer Sheva Israel Univ Calabria DEIS I-87036 Arcavacata Di Rende CS Italy

Default logics are usually used to describe the regular behavior and normal properties of domain elements. In this paper we suggest, conversely, that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected semantical characteristics. These sets of literals are selected among those explicitly embodied in the given knowledge base. Hence, essentially we perceive outlier detection as a knowledge discovery technique. This paper defines the notion of outlier in two related formalisms for specifying defaults: Reiter's default logic and extended disjunctive logic programs. For each of the two formalisms, we show that finding outliers is quite complex. Indeed, we prove that several versions of the outlier detection problem lie over the second level of the polynomial hierarchy. We believe that a thorough complexity analysis, as done here, is a useful preliminary step towards developing effective heuristics and exploring tractable subsets of outlier detection problems. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Default logic disjunctive logic programming Knowledge representation Nonmonotonic reasoning Computational complexity Data mining Outlier detection

来源：评论

学校读者我要写书评

暂无评论

A logic programming approach to knowledge-state planning, II:: The DLV^K system

引用

ARTIFICIAL INTELLIGENCE 2003年第1-2期144卷 157-211页

作者： Eiter, T Faber, W Leone, N Pfeifer, G Polleres, A Univ Calabria Dept Math I-87030 Arcavacata Di Rende CS Italy Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria

In Part I of this series of papers, we have proposed a new logic-based planning language, called K. This language facilitates the description of transitions between states of knowledge and it is well suited for planning under incomplete knowledge. Nonetheless, K also supports the representation of transitions between states of the world (i.e., states of complete knowledge) as a special case, proving to be very flexible. In the present Part II, we describe the DLVK planning system, which implements K on top of the disjunctive logic programming system DLV. This novel planning system allows for solving hard planning problems, including secure planning under incomplete initial states (often called conformant planning in the literature), which cannot be solved at all by other logic-based planning systems such as traditional satisfiability planners. We present a detailed comparison of the DLVK system to several state-of-the-art conformant planning systems, both at the level of system features and on benchmark problems. Our results indicate that, thanks to the power of knowledge-state problem encoding, the DLVK system is competitive even with special purpose conformant planning systems, and it often supplies a more natural and simple representation of the planning problems. (C) 2002 Elsevier Science B.V All rights reserved.

关键词： deductive planning system disjunctive logic programming answer sets knowledge-states incomplete information conformant planning secure planning

来源：评论

学校读者我要写书评

暂无评论

Experimenting with parallelism for the instantiation of ASP programs

引用

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND logic 2008年第1-3期63卷 34-54页

作者： Calimeri, F. Perri, S. Ricca, F. Univ Calabria Dipartimento Matemat I-87036 Arcavacata Di Rende CS Italy

In the last few years, microprocessor technologies have been moving towards multi-core architectures, in order to improve performance as well as reduce power consumption. This makes real Symmetric MultiProcessing (SMP) available even on nondedicated machines, and paves the way to the development of better performing software. Notably, the recent application of Answer Set programming (ASP) in different emerging areas, such as knowledge management or information extraction/integration, shows that performance is a crucial issue also for ASP systems. Among the tasks performed by such systems, the instantiation process, which consists of generating a variable-free program equivalent to the input one, is one of the most expensive from a computational viewpoint, especially in the case of huge input data. In this paper a new strategy exploiting parallelism for the instantiation of ASP programs is proposed. An implementation of this strategy and its integration with the grounding module of the DLV system is discussed. The results of an experimental analysis are also presented, which confirm that the strategy is effective in making ASP instantiation more efficient. (c) 2008 Elsevier Inc. All fights reserved.

关键词： Answer Set programming disjunctive logic programming instantiation parallelism

来源：评论

学校读者我要写书评

暂无评论

Design and implementation of aggregate functions in the DLV system

引用

THEORY AND PRACTICE OF logic programming 2008年第5-6期8卷 545-580页

作者： Faber, Wolfgang Pfeifer, Gerald Leone, Nicola Dellarmi, Tina Ielpa, Giuseppe Univ Calabria Dept Math I-87036 Cosenza Italy

disjunctive logic programming (DLP) is a very expressive formalism. It allows for expressing every property of finite structures that is decidable in the complexity class Sigma(P)(2) (=NPNP). Despite this high expressiveness, there are some simple properties, often arising in real-world applications, which cannot be encoded in a simple and natural manner. Especially properties that require the use of arithmetic operators (like sum, times, or count) on a set or multiset of elements, which satisfy some conditions, cannot be naturally expressed in classic DLP. To overcome this deficiency, we extend DLP by aggregate functions in a conservative way. In particular, we avoid the introduction of constructs with disputed semantics, by requiring aggregates to be stratified. We formally define the semantics of the extended language (called DLPA), and illustrate how it can be profitably used for representing knowledge. Furthermore, we analyze the computational complexity of DLPA, showing that the addition of aggregates does not bring a higher cost in that respect. Finally, we provide an implementation of DLPA in DLV-a state-of-the-art DLP system-and report on experiments which confirm the usefulness of the proposed extension also for the efficiency of computation.

关键词： disjunctive logic programming answer set programming aggregates knowledge representation implementation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：