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

An investigation in parallel execution of answer set programs on distributed memory platforms: Task sharing and dynamic scheduling

引用

COMPUTER LANGUAGES SYSTEMS & STRUCTURES 2010年第2期36卷 158-202页

作者： Pontelli, Enrico Le, Hung Viet Son, Tran Cao New Mexico State Univ Dept Comp Sci MSC CS Las Cruces NM 88003 USA

answer set programming (ASP) is a novel logic programming paradigm, that has already had a profound impact in several application domains, especially in the areas of knowledge representation and reasoning. In spite of the development of excellent inference engines for ASP, efficiency and scalability remain challenging aspects that prevent the use of ASP in various real-world domains. Parallelism has been identified as a natural avenue to address these problems. This paper describes the design of a complete ASP parallel engine, derived from the basic design of the SMODELS architecture. The paper places emphasis on addressing the problem of the irregular structure of the search trees generated by typical ASP computations (in a SMODELS-like computation), which requires the use of dynamic load balancing mechanisms. The paper provides a systematic investigation of alternative strategies for dynamic scheduling and task sharing. These are the two components that more directly affect the efficiency of a parallel engine. (c) 2009 Elsevier Ltd. All rights reserved.

关键词： Logic programming answer set programming Parallelism Scheduling

来源：评论

学校读者我要写书评

暂无评论

Harnessing Incremental answer set Solving for Reasoning in Assumption-Based Argumentation

引用

THEORY AND PRACTICE OF LOGIC programming 2021年第6期21卷 717-734页

作者： Lehtonen, Tuomo Wallner, Johannes P. Jarvisalo, Matti Univ Helsinki Helsinki Finland Graz Univ Technol Graz Austria

Assumption-based argumentation (ABA) is a central structured argumentation formalism. As shown recently, answer set programming (ASP) enables efficiently solving NP-hard reasoning tasks of ABA in practice, in particular in the commonly studied logic programming fragment of ABA. In this work, we harness recent advances in incremental ASP solving for developing effective algorithms for reasoning tasks in the logic programming fragment of ABA that are presumably hard for the second level of the polynomial hierarchy, including skeptical reasoning under preferred semantics as well as preferential reasoning. In particular, we develop non-trivial counterexample-guided abstraction refinement procedures based on incremental ASP solving for these tasks. We also show empirically that the procedures are significantly more effective than previously proposed algorithms for the tasks.

关键词： answer set programming incremental answer set solving assumption-based argumentation structured argumentation algorithms experimental evaluation

来源：评论

学校读者我要写书评

暂无评论

Boosting answer set Optimization with Weighted Comparator Networks

引用

THEORY AND PRACTICE OF LOGIC programming 2020年第4期20卷 512-551页

作者： Bomanson, Jori Janhunen, Tomi Aalto Univ Dept Comp Sci FI-00076 Aalto Finland Tampere Univ Informat Technol & Commun Sci FI-33014 Tampere Finland

answer set programming (ASP) is a paradigm for modeling knowledge-intensive domains and solving challenging reasoning problems. In ASP solving, a typical strategy is to preprocess problem instances by rewriting complex rules into simpler ones. Normalization is a rewriting process that removes extended rule types altogether in favor of normal rules. Recently, such techniques led to optimization rewriting in ASP, where the goal is to boost answer set optimization by refactoring the optimization criteria of interest. In this paper, we present a novel, general, and effective technique for optimization rewriting based on comparator networks which are specific kinds of circuits for reordering the elements of vectors. The idea is to connect an ASP encoding of a comparator network to the literals being optimized and to redistribute the weights of these literals over the structure of the network. The encoding captures information about the weight of an answer set in auxiliary atoms in a structured way that is proven to yield exponential improvements during branch-and-bound optimization on an infinite family of example programs. The used comparator network can be tuned freely, for example, to find the best size for a given benchmark class. Experiments show accelerated optimization performance on several benchmark problems.

关键词： answer set programming comparator network normalization optimization rewriting translation

来源：评论

学校读者我要写书评

暂无评论

Identification of biological regulatory networks from Process Hitting models

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期568卷 49-71页

作者： Folschette, Maxime Pauleve, Loic Inoue, Katsumi Magnin, Morgan Roux, Olivier LUNAM Univ Ecole Cent Nantes IRCCyN UMR CNRS 6597 Inst Rech Commun & Cybernet Nantes F-44321 Nantes 3 France Res Org Informat & Syst Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan Univ Paris 11 Lab Rech Informat UMR CNRS 8623 F-91405 Orsay France

Qualitative formalisms offer a well-established alternative to the more traditionally used differential equation models of Biological Regulatory Networks (BRNs). These formalisms led to numerous theoretical works and practical tools to understand emerging behaviors. The analysis of the dynamics of very large models is however a rather hard problem, which led us to previously introduce the Process Hitting framework (PH), which is a particular class of nondeterministic asynchronous automata network (or safe Petri nets). Its major advantage lies in the efficiency of several static analyses recently designed to assess dynamical properties, making it possible to tackle very large models. In this paper, we address the formal identification of qualitative models of BRNs from PH models. First, the inference of the Interaction Graph from a PH model summarizes the signed influences between the components that are effective for the dynamics. Second, we provide the inference of all Rene Thomas models of BRNs that are compatible with a given PH. As the PH allows the specification of nondeterministic interactions between components, our inference emphasizes the ability of PH to deal with large BRNs with incomplete knowledge on interactions, where Thomas' approach fails because of the combinatorics of parameters. The inference of corresponding Thomas models is implemented using answer set programming, which allows in particular an efficient enumeration of (possibly numerous) compatible parameterizations. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Qualitative modeling Model abstraction Interaction Graph Rene Thomas' parameters answer set programming

来源：评论

学校读者我要写书评

暂无评论

Generating explanations for biomedical queries

引用

THEORY AND PRACTICE OF LOGIC programming 2015年第1期15卷 35-78页

作者： Erdem, Esra Oztok, Umut Sabanci Univ TR-34956 Istanbul Turkey

We introduce novel mathematical models and algorithms to generate (shortest or k different) explanations for biomedical queries, using answer set programming. We implement these algorithms and integrate them in BIOQUERY-ASP. We illustrate the usefulness of these methods with some complex biomedical queries related to drug discovery, over the biomedical knowledge resources PHARMGKB, DRUGBANK, BIOGRID, CTD, SIDER, DISEASE ONTOLOGY, and ORPHADATA.

关键词： answer set programming explanation generation query answering biomedical queries

来源：评论

学校读者我要写书评

暂无评论

Using ASP for knowledge management with user authorization

引用

DATA & KNOWLEDGE ENGINEERING 2010年第8期69卷 737-762页

作者： Zhao, Lingzhong Qian, Junyan Chang, Liang Cai, Guoyong Guilin Univ Elect Technol Sch Comp & Control Guilin 541004 Peoples R China Wuhan Univ State Key Lab Software Engn Wuhan 430072 Peoples R China

Unlike conventional rule based knowledge bases (KBs) that support monotonic reasoning, a key correctness issue, i.e. the correctness of a sub-KB with respect to the full KB, arises when using a KB represented by non-monotonic reasoning languages such as answer set programming (ASP). Since a user may have rights to access only a subset of a KB, the non-monotonic nature of ASP may cause the occurrence of consequences, which are erroneous in the sense that the consequences are not reasonable in the full KB. This paper proposes an approach dealing with the problem. The main idea is to let the usage of Closed World Assumptions (CWAs) for literals in a KB satisfy certain constraints. Two kinds of access right propositions are created, rule retrieval right propositions to control the access to rules, and CWA right propositions to control the usage of CWAs for literals. Based on these right propositions, this paper first defines an algorithm for translating an original KB into a KB tagged by right propositions, and then discusses the right dependency in a KB and proposes methods for checking and obtaining a set of rights that is closed under a set of dependency rules. Finally, several results on the correctness of a set of rights in a KB are presented, which serve as guidelines for the correct use of a KB. As an example, a KB of illness-related financial support for teachers of a university is presented to illustrate the application of our approach. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Authorization Knowledge base Logic programming answer set programming Correctness

来源：评论

学校读者我要写书评

暂无评论

Fuzzy answer sets approximations

引用

THEORY AND PRACTICE OF LOGIC programming 2013年第4-5期13卷 753-767页

作者： Alviano, Mario Penaloza, Rafael Univ Calabria Dept Math & Comp Sci I-87036 Arcavacata Di Rende CS Italy Tech Univ Dresden D-01062 Dresden Germany Ctr Adv Elect Dresden Dresden Germany

Fuzzy answer set programming (FASP) is a recent formalism for knowledge representation that enriches the declarativity of answer set programming by allowing propositions to be graded. To now, no implementations of FASP solvers are available and all current proposals are based on compilations of logic programs into different paradigms, like mixed integer programs or bilevel programs. These approaches introduce many auxiliary variables which might affect the performance of a solver negatively. To limit this downside, operators for approximating fuzzy answer sets can be introduced: Given a FASP program, these operators compute lower and upper bounds for all atoms in the program such that all answer sets are between these bounds. This paper analyzes several operators of this kind which are based on linear programming, fuzzy unfounded sets and source pointers. Furthermore, the paper reports on a prototypical implementation, also describing strategies for avoiding computations of these operators when they are guaranteed to not improve current bounds. The operators and their implementation can be used to obtain more constrained mixed integer or bilevel programs, or even for providing a basis for implementing a native FASP solver. Interestingly, the semantics of relevant classes of programs with unique answer sets, like positive programs and programs with stratified negation, can be already computed by the prototype without the need for an external tool.

关键词： fuzzy logic answer set programming search-space pruning operators

来源：评论

学校读者我要写书评

暂无评论

Justifications for logic programs under answer set semantics

引用

THEORY AND PRACTICE OF LOGIC programming 2009年第1期9卷 1-56页

作者： Pontelli, Enrico Son, Tran Cao Elkhatib, Omar New Mexico State Univ Dept Comp Sci Las Cruces NM 88003 USA

The paper introduces the notion of offline justification for answer set programming (ASP). Justifications provide a graph-based explanation of the truth value of an atom with respect to a given answer set. The paper extends also this notion to provide justification of atoms during the computation of an answer set (on-line justification) and presents an integration of online justifications within the computation model Of SMODELS. Offline and online justifications provide useful tools to enhance understanding of ASP, and they offer a basic data structure to support methodologies and tools for debugging answer set programs. A preliminary implementation has been developed in ASP - PROLOG.

关键词： answer set programming justification offline justification online justification

来源：评论

学校读者我要写书评

暂无评论

Symmetry-breaking answer set solving

引用

AI COMMUNICATIONS 2011年第2期24卷 177-194页

作者： Drescher, Christian Tifrea, Oana Walsh, Toby NICTA Sydney NSW Australia Univ New S Wales Sydney NSW Australia Free Univ Bozen Bolzano Fac Comp Sci Bolzano Italy

We investigate the role of symmetry detection and symmetry breaking in answer set programming to eliminate symmetric parts of the search space and, thereby, simplify the solution process. We reduce symmetry detection to a graph automorphism problem which allows us to extract symmetries of a logic program from the symmetries of the constructed coloured graph. The correctness of our reduction is proven. We also propose an encoding of symmetry-breaking constraints in terms of permutation cycles and use only generators in this process to implicitly represent symmetries with exponential compression. These ideas are formulated as preprocessing and implemented in a completely automated flow that first detects symmetries from a given answer set program, adds symmetry-breaking constraints, and can be applied to any existing answer set solver. We demonstrate computational impact on benchmarks versus direct application of the solver.

关键词： answer set programming symmetry breaking graph automorphism problem

来源：评论

学校读者我要写书评

暂无评论

Exact and heuristic methods for solving Boolean games

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2017年第1期31卷 66-106页

作者： De Clercq, Sofie Bauters, Kim Schockaert, Steven Mihaylov, Mihail Nowe, Ann De Cock, Martine Univ Ghent Dept Appl Math CS & Stat Ghent Belgium Queens Univ Sch Elect Elect Engn & CS Belfast Antrim North Ireland Cardiff Univ Sch Comp Sci & Informat Cardiff S Glam Wales Vrije Univ Brussel Artificial Intelligence Lab Brussels Belgium Univ Washington Ctr Data Sci Tacoma WA USA

Boolean games are a framework for reasoning about the rational behavior of agents whose goals are formalized using propositional formulas. Compared to normal form games, a well-studied and related game framework, Boolean games allow for an intuitive and more compact representation of the agents' goals. So far, Boolean games have been mainly studied in the literature from the Knowledge Representation perspective, and less attention has been paid on the algorithmic issues underlying the computation of solution concepts. Although some suggestions for solving specific classes of Boolean games have been made in the literature, there is currently no work available on the practical performance. In this paper, we propose the first technique to solve general Boolean games that does not require an exponential translation to normal-form games. Our method is based on disjunctive answer set programming and computes solutions (equilibria) of arbitrary Boolean games. It can be applied to a wide variety of solution concepts, and can naturally deal with extensions of Boolean games such as constraints and costs. We present detailed experimental results in which we compare the proposed method against a number of existing methods for solving specific classes of Boolean games, as well as adaptations of methods that were initially designed for normal-form games. We found that the heuristic methods that do not require all payoff matrix entries performed well for smaller Boolean games, while our ASP based technique is faster when the problem instances have a higher number of agents or action variables.

关键词： Boolean games Heuristic methods answer set programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：