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

Non-deterministic Approximation Operators: Ultimate Operators, Semi-equilibrium Semantics, and Aggregates

THEORY AND PRACTICE OF logic programming 2023年第4期23卷 632-647页

作者： Heyninck, Jesse Bogaerts, Bart Open Univ Heerlen Netherlands Vrij Univ Brussels Brussels Belgium

Approximation fixpoint theory (AFT) is an abstract and general algebraic framework for studying the semantics of non-monotonic logics. In recent work, AFT was generalized to non-deterministic operators, that is, operators whose range are sets of elements rather than single elements. In this paper, we make three further contributions to non-deterministic AFT: (1) we define and study ultimate approximations of non-deterministic operators, (2) we give an algebraic formulation of the semi-equilibrium semantics by Amendola et al., and (3) we generalize the characterizations of disjunctive logic programs to disjunctive logic programs with aggregates.

关键词： approximation fixpoint theory disjunctive logic programming semi-equilibrium semantics

来源：评论

学校读者我要写书评

暂无评论

More on tractable disjunctive Datalog

引用

JOURNAL OF logic programming 2000年第1-2期46卷 61-101页

作者： Ben-Eliyahu-Zohary, R Palopoli, L Zemlyanker, V Univ Calabria DEIS I-87036 Arcavacata Di Rende CS Italy Ben Gurion Univ Negev Commun Syst Engn Dept IL-84105 Beer Sheva Israel Technion Israel Inst Technol Dept Informat Engn IL-32000 Haifa Israel

Sometimes it is more natural to express knowledge in disjunctive Datalog rather than in ordinary Datalog. Several highly complex variants of disjunctive Datalog have been proposed in the past and their expressive power has been studied. In this paper we investigate tractable fragments of disjunctive Datalog. Algorithms are presented to answer queries defined using these fragments and their complexity analyzed. Furthermore, the expressive power of these tractable subsets is studied. The most expressive of the languages considered here is shown to express, in some sense explained in the paper, all polynomial time queries. This is the first identified fragment of disjunctive Datalog with this property. (C) 2000 Elsevier Science Inc. All rights reserved.

关键词： disjunctive logic programming head-cycle-free programs non-deterministic semantics expressive power of query languages polynomial-time queries

来源：评论

学校读者我要写书评

暂无评论

Outlier detection for simple default theories

引用

ARTIFICIAL INTELLIGENCE 2010年第15期174卷 1247-1253页

作者： Angiulli, Fabrizio Ben-Eliyahu-Zohary, Rachel Palopoli, Luigi Ben Gurion Univ Negev Commun Syst Engn Dept Beer Sheva Israel Univ Calabria DEIS I-87036 Arcavacata Di Rende CS Italy Harvard Univ Div Engn & Appl Sci Cambridge MA 02138 USA

It was noted recently that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected properties. These observations are not explicitly provided in input (as it happens with abduction) but, rather, they are hidden in the given knowledge base. Unfortunately, in the two related formalisms for specifying defaults - Reiter's default logic and extended disjunctive logic programs - the most general outlier detection problems turn out to lie at the third level of the polynomial hierarchy. In this note, we analyze the complexity of outlier detection for two very simple classes of default theories, namely NU and DNU, for which the entailment problem is solvable in polynomial time. We show that, for these classes, checking for the existence of an outlier is anyway intractable. This result contributes to further showing the inherent intractability of outlier detection in default reasoning. (c) 2010 Elsevier B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

Exchange-Repairs Managing Inconsistency in Data Exchange

引用

JOURNAL ON DATA SEMANTICS 2016年第2期5卷 77-97页

作者： ten Cate, Balder Halpert, Richard L. Kolaitis, Phokion G. Univ Calif Santa Cruz Santa Cruz CA 95064 USA LogicBlox Inc Atlanta GA USA IBM Res Almaden San Jose CA USA

In a data exchange setting with target constraints, it is often the case that a given source instance has no solutions. Intuitively, this happens when data sources contain inconsistent or conflicting information that is exposed by the target constraints at hand. In such cases, the semantics of target queries trivialize, because the certain answers of every target query over the given source instance evaluate to "true". The aim of this paper is to introduce and explore a new framework that gives meaningful semantics in such cases using the notion of exchange-repairs. Informally, an exchange-repair of a source instance is another source instance that differs minimally from the first, but has a solution. In turn, exchange-repairs give rise to a natural notion of exchange-repair certain answers (in short, XR-certain answers) for target queries in the context of data exchange with target constraints. After exploring the structural properties of exchange-repairs, we focus on the problem of computing the XR-certain answers of conjunctive queries. We show that for schema mappings specified by source-to-target GAV dependencies and target equality-generating dependencies (egds), the XR-certain answers of a target conjunctive query can be rewritten as the consistent answers (in the sense of standard database repairs) of a union of conjunctive queries over the source schema with respect to a set of egds over the source schema, thus making it possible to use a consistent query answering system to compute XR-certain answers in data exchange. In contrast, we show that this type of rewriting is neither possible for schema mappings specified by source-to-target LAV dependencies and target egds, nor for schema mappings specified by both source-to-target and target GAV dependencies. We then examine the general case of schema mappings specified by source-to-target GLAV constraints, a weakly acyclic set of target tgds and a set of target egds. The main result asserts that, for such sett

关键词： Data exchange Certain answers Database repairs Consistent query answering disjunctive logic programming Stable models

来源：评论

学校读者我要写书评

暂无评论

Enhancing DLV instantiator by backjumping techniques

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2007年第2-4期51卷 195-228页

作者： Perri, Simona Scarcello, Francesco Catalano, Gelsomina Leone, Nicola Univ Calabria Dept Math I-87036 Arcavacata Di Rende Italy Univ Calabria DEIS I-87036 Arcavacata Di Rende Italy

disjunctive logic programming (DLP) is a powerful formalism for knowledge representation and reasoning. The high expressiveness of DLP language, together with the recent availability of some efficient DLP system, has favoured the application of DLP in emerging areas like Knowledge Management and Information Integration. These applications have often to deal with huge input data, and have evidenced the need to improve the efficiency of DLP instantiators. Program instantiation is the first phase of a DLP computation;in this phase, variables are replaced by constants to generate a ground program which is then evaluated by propositional algorithms in the second phase of the computation. The instantiation process may be computationally expensive, and in fact its efficiency has been recognized to be a key issue for solving real-world problems by using disjunctive logic programming. Given a program P, a good instantiation for P is a ground program P' having precisely the same answer sets as P and such that: (1) P' can be computed efficiently from P, and (2) P' does not contain "useless" rules, (P' is as small as possible) and can thus be evaluated efficiently. In this paper, we present a structure-based backjumping algorithm for the instantiation of disjunctive logic programs, that meets the above requirements. In particular, given a rule r to be grounded, our algorithm exploits both the semantical and the structural information about r for computing efficiently the ground instances of r, avoiding the generation of "useless" rules. That is, from each general rule r, we compute only a relevant subset of its ground instances, avoiding the generation of "useless" instances, while fully preserving the semantic of the program. We have implemented this algorithm in DLV-the state-of-the-art implementation of DLP-and we have carried out an experimentation activity on an ample collection of benchmark problems. The experimental results are very positive: the new technique improves s

关键词： artificial intelligence logic programming nonmonotonic reasoning disjunctive logic programming answer set programming deductive databases stable model semantics

来源：评论

学校读者我要写书评

暂无评论

Stable-unstable semantics: Beyond NP with normal logic programs

引用

THEORY AND PRACTICE OF logic programming 2016年第5-6期16卷 570-586页

作者： Bogaerts, Bart Janhunen, Tomi Tasharrofi, Shahab Aalto Univ HIIT Dept Comp Sci FI-00076 Aalto Finland

Standard answer set programming (ASP) targets at solving search problems from the first level of the polynomial time hierarchy (PH). Tackling search problems beyond NP using ASP is less straightforward. The class of disjunctive logic programs offers the most prominent way of reaching the second level of the PH, but encoding respective hard problems as disjunctive programs typically requires sophisticated techniques such as saturation or meta-interpretation. The application of such techniques easily leads to encodings that are inaccessible to non-experts. Furthermore, while disjunctive ASP solvers often rely on calls to a (co-)NP oracle, it may be difficult to detect from the input program where the oracle is being accessed. In other formalisms, such as Quantified Boolean Formulas (QBFs), the interface to the underlying oracle is more transparent as it is explicitly recorded in the quantifier prefix of a formula. On the other hand, ASP has advantages over QBFs from the modeling perspective. The rich high-level languages such as ASP-Core-2 offer a wide variety of primitives that enable concise and natural encodings of search problems. In this paper, we present a novel logic programming-based modeling paradigm that combines the best features of ASP and QBFs. We develop so-called combined logic programs in which oracles are directly cast as (normal) logic programs themselves. Recursive incarnations of this construction enable logic programming on arbitrarily high levels of the PH. We develop a proof-of-concept implementation for our new paradigm.

关键词： disjunctive logic programming polynomial hierarchy quantified Boolean formulas

来源：评论

学校读者我要写书评

暂无评论

OntoDLV: An ASP-based System for Enterprise Ontologies

引用

JOURNAL OF logic AND COMPUTATION 2009年第4期19卷 643-670页

作者： Ricca, Francesco Gallucci, Lorenzo Schindlauer, Roman Dell'Armi, Tina Grasso, Giovanni Leone, Nicola Univ Calabria Dept Math I-87036 Arcavacata Di Rende CS Italy Univ Calabria Exeura SRL I-87036 Arcavacata Di Rende CS Italy

Enterprise/Corporate ontologies are widely adopted to conceptualize business enterprise information. In this area, the semantic peculiarities of Answer Set programming (ASP), like the Closed World Assumption (CWA) and the Unique Name Assumption (UNA), are more appropriate than the OntologyWeb Language (OWL) assumptions, also because such ontologies frequently stem from relational databases, where both CWA and UNA are adopted. This article presents OntoDLV, a system based on ASP for the specification and reasoning on enterprise ontologies. OntoDLV implements a powerful ontology representation language, called OntoDLP, extending (disjunctive) ASP with all the main ontology features including classes, inheritance, relations and axioms. OntoDLP is strongly typed, and includes also complex type constructors, like lists and sets. Importantly, OntoDLV supports a powerful interoperability mechanism with OWL, allowing the user to retrieve information from OWL ontologies, and build rule-based reasoning on top of OWL ontologies. The system is already used in a number of real-world applications including agent-based systems, information extraction, and text classification.

关键词： logic programming disjunctive logic programming answer set programming ontology languages enterprise ontologies OWL

来源：评论

学校读者我要写书评

暂无评论

Pushing goal derivation in DLP computations 5th

引用

5th International Conference on logic programming and Nonmonotonic Reasoning (LPNMR 99)

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

ISBN: (纸本)3540667490

dlv is a knowledge representation system, based on disjunctive logic programming, 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.

关键词： disjunctive logic programming algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

Dynamic Magic Sets for Programs with Monotone Recursive Aggregates

引用

11th International Conference on logic programming and Nonmonotonic Reasoning (LPNMR)

作者： Alviano, Mario Greco, Gianluigi Leone, Nicola Univ Calabria Dept Math I-87036 Arcavacata Di Rende CS Italy

ISBN: (纸本)9783642208942;9783642208959

disjunctive logic programming (DLP) is an extension of Datalog that allows for disjunction in rule head and nonmonotonic negation in bodies. All of the queries in the second level of the polynomial hierarchy can be expressed in this language. However, DLP does not allow for representing properties which involve sets of data in a natural way. Extending the language by introducing aggregate functions has been proposed in the literature to overcome this lack, then leading to the language DLPA,(sic). In particular, DLPA,(sic) allows for using recursive aggregates, which naturally arise in many practical application scenarios. An aggregate is recursive if its aggregate set depends on the evaluation of the aggregate itself. The evaluation of programs with aggregates is hard, especially when aggregates are recursive, optimization techniques are highly needed to make these programs usable in real-world applications. In this paper, we focus on the optimization of queries over programs with recursive aggregates. In particular, we design an extension of the Dynamic Magic Set (DMS) technique to programs with stratified negation and monotone recursive aggregates, and we demonstrate the correctness of the proposed technique. For assessing the effectiveness of the new technique, we consider a standard benchmark for recursive aggregates, referred to as Company Controls, along with a couple of benchmarks involving aggregates over the WordNet database. Experimental results confirm the effectiveness of our technique.

关键词： disjunctive logic programming recursive aggregates Magic Sets

来源：评论

学校读者我要写书评

暂无评论

Stable-unstable semantics: Beyond NP with normal logic programs

Stable-unstable semantics: Beyond NP with normal logic progr...

引用

32nd International Conference on logic programming (ICLP)

作者： Bogaerts, Bart Janhunen, Tomi Tasharrofi, Shahab Aalto Univ HIIT Dept Comp Sci FI-00076 Aalto Finland

关键词： disjunctive logic programming polynomial hierarchy quantified Boolean formulas

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：