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

20th Workshop on Empirically Successful Classical Automated Reasoning

作者： Giunchiglia, Enrico Lierler, Yuliya Maratea, Marco Univ Genoa DIST STAR Lab I-16145 Genoa Italy Univ Erlangen Nurnberg Inst Informat Erlangen Germany Univ Calabria Dept Math I-87036 Arcavacata Di Rende CS Italy

answer set programming ( ASP) emerged in the late 1990s as a new logic programming paradigm that has been successfully applied in various application domains. Also motivated by the availability of efficient solvers for propositional satisfiability ( SAT), various reductions from logic programs to SAT were introduced. All these reductions, however, are limited to a subclass of logic programs or introduce new variables or may produce exponentially bigger propositional formulas. In this paper, we present a SAT-based procedure, called ASP-SAT, that ( 1) deals with any (nondisjunctive) logic program, ( 2) works on a propositional formula without additional variables ( except for those possibly introduced by the clause form transformation), and ( 3) is guaranteed to work in polynomial space. From a theoretical perspective, we prove soundness and completeness of ASP-SAT. From a practical perspective, we have ( 1) implemented ASP-SAT in CMODELS, ( 2) extended the basic procedures in order to incorporate the most popular SAT reasoning strategies, and ( 3) conducted an extensive comparative analysis involving other state-of-the-art answer set solvers. The experimental analysis shows that our solver is competitive with the other solvers we considered and that the reasoning strategies that work best on 'small but hard' problems are ineffective on 'big but easy' problems and vice versa.

关键词： answer set programming propositional satisfiability

来源：评论

学校读者我要写书评

暂无评论

answer set programming as a modeling language for course timetabling

Answer set programming as a modeling language for course tim...

引用

29th International Conference on Logic programming ICLP

作者： Banbara, Mutsunori Soh, Takehide Tamura, Naoyuki Inoue, Katsumi Schaub, Torsten Kobe Univ Nada Ku Kobe Hyogo 6578501 Japan Res Org Informat & Syst Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan Univ Potsdam D-14482 Potsdam Germany

The course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. The modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty (S, V, C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared with the previous best known bounds.

关键词： answer set programming educational timetabling course timetabling

来源：评论

学校读者我要写书评

暂无评论

ASPER: answer set programming Enhanced Neural Network Models for Joint Entity-Relation Extraction

引用

THEORY AND PRACTICE OF LOGIC programming 2023年第4期23卷 765-781页

作者： Le, Trung Hoang Cao, Huiping Cao Son, Tran New Mexico State Univ Dept Comp Sci Las Cruces NM 88003 USA

A plethora of approaches have been proposed for joint entity-relation (ER) extraction. Most of these methods largely depend on a large amount of manually annotated training data. However, manual data annotation is time-consuming, labor-intensive, and error-prone. Human beings learn using both data (through induction) and knowledge (through deduction). answer set programming (ASP) has been a widely utilized approach for knowledge representation and reasoning that is elaboration tolerant and adept at reasoning with incomplete information. This paper proposes a new approach, ASP-enhanced Entity-Relation extraction (ASPER), to jointly recognize entities and relations by learning from both data and domain knowledge. In particular, ASPER takes advantage of the factual knowledge (represented as facts in ASP) and derived knowledge (represented as rules in ASP) in the learning process of neural network models. We have conducted experiments on two real datasets and compare our method with three baselines. The results show that our ASPER model consistently outperforms the baselines.

关键词： joint entity-relation extraction semi-supervised learning answer set programming knowledge-enhanced models

来源：评论

学校读者我要写书评

暂无评论

Forgetting in answer set programming - A Survey

引用

THEORY AND PRACTICE OF LOGIC programming 2023年第1期23卷 111-156页

作者： Goncalves, Ricardo Knorr, Matthias Leite, Joao Univ Nova Lisboa NOVA LINCS Dept Informat Fac Ciencias & Tecnol Lisbon Portugal

Forgetting - or variable elimination - is an operation that allows the removal, from a knowledge base, of middle variables no longer deemed relevant. In recent years, many different approaches for forgetting in answer set programming have been proposed, in the form of specific operators, or classes of such operators, commonly following different principles and obeying different properties. Each such approach was developed to address some particular view on forgetting, aimed at obeying a specific set of properties deemed desirable in such view, but a comprehensive and uniform overview of all the existing operators and properties is missing. In this article, we thoroughly examine existing properties and (classes of) operators for forgetting in answer set programming, drawing a complete picture of the landscape of these classes of forgetting operators, which includes many novel results on relations between properties and operators, including considerations on concrete operators to compute results of forgetting and computational complexity. Our goal is to provide guidance to help users in choosing the operator most adequate for their application requirements.

关键词： forgetting answer set programming logic programs

来源：评论

学校读者我要写书评

暂无评论

Optimizing phylogenetic supertrees using answer set programming

引用

THEORY AND PRACTICE OF LOGIC programming 2015年第4-5期15卷 604-619页

作者： Koponen, Laura Oikarinen, Emilia Janhunen, Tomi Saila, Laura Aalto Univ HIIT FI-00076 Aalto Finland Aalto Univ Dept Comp Sci FI-00076 Aalto Finland Univ Helsinki Dept Geosci & Geog FIN-00014 Helsinki Finland

The supertree construction problem is about combining several phylogenetic trees with possibly conflicting information into a single tree that has all the leaves of the source trees as its leaves and the relationships between the leaves are as consistent with the source trees as possible. This leads to an optimization problem that is computationally challenging and typically heuristic methods, such as matrix representation with parsimony (MRP), are used. In this paper we consider the use of answer set programming to solve the supertree construction problem in terms of two alternative encodings. The first is based on an existing encoding of trees using substructures known as quartets, while the other novel encoding captures the relationships present in trees through direct projections. We use these encodings to compute a genus-level supertree for the family of cats (Felidae). Furthermore, we compare our results to recent supertrees obtained by the MRP method.

关键词： answer set programming phylogenetic supertree quartets projections Felidae

来源：评论

学校读者我要写书评

暂无评论

Efficiently Querying RDF(S) Ontologies with answer set programming

引用

JOURNAL OF LOGIC AND COMPUTATION 2009年第4期19卷 671-695页

作者： Ianni, Giovambattista Martello, Alessandra Panetta, Claudio Terracina, Giorgio Univ Calabria Dipartimento Matemat I-87036 Arcavacata Di Rende CS Italy Vienna Univ Technol Inst Informat Syst 184 3 A-1040 Vienna Austria

Ontologies are pervading many areas of knowledge representation and management. To date, most research efforts have been spent on the development of sufficiently expressive languages for the representation and querying of ontologies;however, querying efficiency has received attention only recently, especially for ontologies referring to large amounts of data. In fact, it is still uncertain how reasoning tasks will scale when applied on massive amounts of data. This work is a first step toward this setting: it first shows that Resource Description Framework(Schema) [RDF(S)] ontologies can be expressed, without loss of semantics, into answer set programming (ASP). Then, based on a previous result showing that the SPARQL query language (a candidate W3C recommendation for RDF(S) ontologies) can be mapped to a rule-based language, it shows that efficient querying of big ontologies can be accomplished with a database oriented extension of the well known ASP system DLV, which we recently developed. Results reported in the article show that our proposed framework is promising for the improvement of both scalability and expressiveness of available RDF(S) storage and query systems.

关键词： answer set programming knowledge representation RDF Ontologies

来源：评论

学校读者我要写书评

暂无评论

Computing preferred answer sets by meta-interpretation in answer set programming

引用

THEORY AND PRACTICE OF LOGIC programming 2003年第4%2B5期3卷 463-498页

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

Most recently, answer set programming (ASP) has been attracting interest as a new paradigm for problem solving. An important aspect, for which several approaches have been presented, is the handling of preferences between rules. In this paper, we consider the problem of implementing preference handling approaches by means of meta-interpreters in answer set programming. In particular, we consider the preferred answer set approaches by Brewka and Eiter, by Delgrande, Schaub and Tompits, and by Wang, Zhou and Lin. We present suitable meta-interpreters for these semantics using DLV, which is an efficient engine for ASP. Moreover, we also present a meta-interpreter for the weakly preferred answer set approach by Brewka and Eiter, which uses the weak constraint feature of DLV as a tool for expressing and solving an underlying optimization problem. We also consider advanced meta-interpreters, which make use of graph-based characterizations and often allow for more efficient computations. Our approach shows the suitability of ASP in general and of DLV in particular for fast prototyping. This can be fruitfully exploited for experimenting with new languages and knowledge-representation formalisms.

关键词： answer set programming meta-interpretation preference semantics

来源：评论

学校读者我要写书评

暂无评论

Analyzing XACML policies using answer set programming

引用

INTERNATIONAL JOURNAL OF INFORMATION SECURITY 2019年第4期18卷 465-479页

作者： Rezvani, Mohsen Rajaratnam, David Ignjatovic, Aleksandar Pagnucco, Maurice Jha, Sanjay Shahrood Univ Technol Fac Comp Engn Shahrood Iran Univ New South Wales Sch Comp Sci & Engn Sydney NSW Australia

With the tremendous growth of Web applications and services, eXtensible Access Control Markup Language (XACML) has been broadly adopted to specify Web access control policies. However, when the policies are large or defined by multiple authorities, it has proved difficult to analyze errors and vulnerabilities in a manual fashion. Recent advances in the answer set programming (ASP) paradigm have provided a powerful problem-solving formalism that is capable of dealing with policy verification. In this paper, we employ ASP to analyze various properties of XACML policies. To this end, we first propose a structured mechanism to translate a XACML policy into an ASP program. Then, we leverage the features of off-the-shelf ASP solvers to specify and verify a wide range of properties of a XACML policy, including redundancy, conflicts, refinement, completeness, reachability, and usefulness. We present an empirical evaluation of the effectiveness and efficiency of a policy analysis tool implemented on top of the Clingo ASP solver. The evaluation results show that our approach is computationally more efficient compared with existing approaches.

关键词： XACML Policy analysis Anomaly detection answer set programming

来源：评论

学校读者我要写书评

暂无评论

aspeed: Solver scheduling via answer set programming

引用

THEORY AND PRACTICE OF LOGIC programming 2015年第1期15卷 117-142页

作者： Hoos, Holger Kaminski, Roland Lindauer, Marius Schaub, Torsten Univ British Columbia Dept Comp Sci Vancouver BC V5Z 1M9 Canada Univ Potsdam Inst Informat Potsdam Germany

Although Boolean Constraint Technology has made tremendous progress over the last decade, the efficacy of state-of-the-art solvers is known to vary considerably across different types of problem instances, and is known to depend strongly on algorithm parameters. This problem was addressed by means of a simple, yet effective approach using handmade, uniform, and unordered schedules of multiple solvers in ppfolio, which showed very impressive performance in the 2011 Satisfiability Testing (SAT) Competition. Inspired by this, we take advantage of the modeling and solving capacities of answer set programming (ASP) to automatically determine more refined, that is, nonuniform and ordered solver schedules from the existing benchmarking data. We begin by formulating the determination of such schedules as multi-criteria optimization problems and provide corresponding ASP encodings. The resulting encodings are easily customizable for different settings, and the computation of optimum schedules can mostly be done in the blink of an eye, even when dealing with large runtime data sets stemming from many solvers on hundreds to thousands of instances. Also, the fact that our approach can be customized easily enabled us to swiftly adapt it to generate parallel schedules for multi-processor machines.

关键词： algorithm schedules answer set programming portfolio-based solving

来源：评论

学校读者我要写书评

暂无评论

Solving stable matching problems using answer set programming

引用

THEORY AND PRACTICE OF LOGIC programming 2016年第3期16卷 247-268页

作者： De Clercq, Sofie Schockaert, Steven De Cock, Martine Nowe, Ann Univ Ghent Dept Appl Math Comp Sci & Stat Ghent Belgium Cardiff Univ Sch Comp Sci & Informat Cardiff S Glam Wales UW Tacoma Ctr Data Sci Tacoma WA USA Vrije Univ Brussel Computat Modeling Lab Brussels Belgium

Since the introduction of the stable marriage problem (SMP) by Gale and Shapley (1962), several variants and extensions have been investigated. While this variety is useful to widen the application potential, each variant requires a new algorithm for finding the stable matchings. To address this issue, we propose an encoding of the SMP using answer set programming (ASP), which can straightforwardly be adapted and extended to suit the needs of specific applications. The use of ASP also means that we can take advantage of highly efficient off-the-shelf solvers. To illustrate the flexibility of our approach, we show how our ASP encoding naturally allows us to select optimal stable matchings, i.e. matchings that are optimal according to some user-specified criterion. To the best of our knowledge, our encoding offers the first exact implementation to find sex-equal, minimum regret, egalitarian or maximum cardinality stable matchings for SMP instances in which individuals may designate unacceptable partners and ties between preferences are allowed.

关键词： answer set programming Logic rules Stable marriage problem Optimal stable matchings

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：