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

answer-set programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling

THEORY AND PRACTICE OF LOGIC programming 2023年第6期23卷 1281-1306页

作者： Eiter, Thomas Geibinger, Tobias Musliu, Nysret Oetsch, Johannes Skocovsky, Peter Stepanova, Daria Vienna Univ Technol TU Wien Inst L & Computat Vienna Austria Robert Bosch Campus 1 D-71272 Renningen Germany

We deal with a challenging scheduling problem on parallel machines with sequence-dependent setup times and release dates from a real-world application of semiconductor work-shop production. There, jobs can only be processed by dedicated machines, thus few machines can determine the makespan almost regardless of how jobs are scheduled on the remaining ones. This causes problems when machines fail and jobs need to be rescheduled. Instead of optimising only the makespan, we put the individual machine spans in non-ascending order and lexicographically minimise the resulting tuples. This achieves that all machines complete as early as possible and increases the robustness of the schedule. We study the application of answer-set programming (ASP) to solve this problem. While ASP eases modelling, the combination of timing constraints and the considered objective function challenges current solving technology. The former issue is addressed by using an extension of ASP by difference logic. For the latter, we devise different algorithms that use multi-shot solving. To tackle industrial-sized instances, we study different approximations and heuristics. Our experimental results show that ASP is indeed a promising knowledge representation and reasoning (KRR) paradigm for this problem and is competitive with state-of-the-art constraint programming (CP) and Mixed-Integer programming (MIP) solvers.

关键词： answer-set programming parallel machine scheduling lexicographical optimisation

来源：评论

学校读者我要写书评

暂无评论

answer-set programming encodings for argumentation frameworks

引用

ARGUMENT & COMPUTATION 2010年第2期1卷 147-177页

作者： Egly, Uwe Gaggl, Sarah Alice Woltran, Stefan Vienna Univ Technol Inst Informat Syst 184 Favoritenstr 9-11 A-1040 Vienna Austria

answer-set programming (ASP) has emerged as a declarative programming paradigm where problems are encoded as logic programs, such that the so-called answer sets of theses programs represent the solutions of the encoded problem. The efficiency of the latest ASP solvers reached a state that makes them applicable for problems of practical importance. Consequently, problems from many different areas, including diagnosis, data integration, and graph theory, have been successfully tackled viaASP. In this work, we present such ASP-encodings for problems associated to abstract argumentation frameworks (AFs) and generalisations thereof. Our encodings are formulated as fixed queries, such that the input is the only part depending on the actual AF to process. We illustrate the functioning of this approach, which is underlying a new argumentation system called ASPARTIX in detail and show its adequacy in terms of computational complexity.

关键词： abstract argumentation frameworks answer-set programming implementation

来源：评论

学校读者我要写书评

暂无评论

A multi-engine approach to answer-set programming

引用

THEORY AND PRACTICE OF LOGIC programming 2014年第6期14卷 841-868页

作者： Maratea, Marco Pulina, Luca Ricca, Francesco Univ Genoa DIBRIS I-16145 Genoa Italy Univ Sassari POLCOMING I-07100 Sassari Italy Univ Calabria Dipartimento Matemat I-87030 Arcavacata Di Rende Italy

answer-set programming (ASP) is a truly declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming, which has been recently employed in many applications. The development of efficient ASP systems is, thus, crucial. Having in mind the task of improving the solving methods for ASP, there are two usual ways to reach this goal: (i) extending state-of-the-art techniques and ASP solvers or (ii) designing a new ASP solver from scratch. An alternative to these trends is to build on top of state-of-the-art solvers, and to apply machine learning techniques for choosing automatically the "best" available solver on a per-instance basis. In this paper, we pursue this latter direction. We first define a set of cheap-to-compute syntactic features that characterize several aspects of ASP programs. Then, we apply classification methods that, given the features of the instances in a training set and the solvers' performance on these instances, inductively learn algorithm selection strategies to be applied to a test set. We report the results of a number of experiments considering solvers and different training and test sets of instances taken from the ones submitted to the "System Track" of the Third ASP Competition. Our analysis shows that by applying machine learning techniques to ASP solving, it is possible to obtain very robust performance: our approach can solve more instances compared with any solver that entered the Third ASP Competition.

关键词： answer-set programming automated algorithm selection multi-engine solvers

来源：评论

学校读者我要写书评

暂无评论

A common view on strong, uniform, and other notions of equivalence in answer-set programming

引用

THEORY AND PRACTICE OF LOGIC programming 2008年第2期8卷 217-234页

作者： Woltran, Stefan Vienna Univ Technol Inst Informat Syst 184 2 A-1040 Vienna Austria

Logic programming under the answer-set semantics nowadays deals with numerous different notions of program equivalence. This is due to the fact that equivalence for substitution (known as strong equivalence) and ordinary equivalence are different concepts. The former holds, given programs P and Q, iff P can be faithfully replaced by Q within any context R, while the latter holds iff P and Q provide the same output, that is, they have the same answer sets. Notions in between strong and ordinary equivalence have been introduced as theoretical tools to compare incomplete programs and are defined by either restricting the syntactic structure of the considered context programs R or by bounding the set A of atoms allowed to occur in R (relativized equivalence). For the latter approach, different v yield properly different equivalence notions, in general. For the former approach, however, it turned out that any "reasonable" syntactic restriction to R coincides with either ordinary, strong, or uniform equivalence (for uniform equivalence, the context ranges over arbitrary sets of facts, rather than program rules). In this paper, we propose a parameterization for equivalence notions which takes care of both such kinds of restrictions simultaneously by bounding, on the one hand, the atoms which are allowed to occur in the rule heads of the context and, on the other hand, the atoms which are allowed to occur in the rule bodies of the context. We introduce a general semantical characterization which includes known ones as SE-models (for strong equivalence) or UE-models (for uniform equivalence) as special cases. Moreover, we provide complexity bounds for the problem in question and sketch a possible implementation method making use of dedicated systems for checking ordinary equivalence.

关键词： answer-set programming strong equivalence relativized equivalence

来源：评论

学校读者我要写书评

暂无评论

Improved answer-set programming encodings for abstract argumentation

引用

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

作者： Gaggl, Sarah A. Manthey, Norbert Ronca, Alessandro Wallner, Johannes P. Woltran, Stefan Tech Univ Dresden Dresden Germany Univ Roma La Sapienza Rome Italy Univ Helsinki Dept Comp Sci HIIT FIN-00014 Helsinki Finland Vienna Univ Technol Vienna Austria

The design of efficient solutions for abstract argumentation problems is a crucial step towards advanced argumentation systems. One of the most prominent approaches in the literature is to use answer-set programming (ASP) for this endeavor. In this paper, we present new encodings for three prominent argumentation semantics using the concept of conditional literals in disjunctions as provided by the ASP-system clingo. Our new encodings are not only more succinct than previous versions, but also outperform them on standard benchmarks.

关键词： answer-set programming Abstract Argumentation Implementation ASPARTIX

来源：评论

学校读者我要写书评

暂无评论

Tractable answer-set programming with weight constraints: bounded treewidth is not enough

引用

THEORY AND PRACTICE OF LOGIC programming 2014年第2期14卷 141-164页

作者： Pichler, Reinhard Ruemmele, Stefan Szeider, Stefan Woltran, Stefan Vienna Univ Technol Vienna Austria

Cardinality constraints or, more generally, weight constraints are well recognized as an important extension of answer-set programming. Clearly, all common algorithmic tasks related to programs with cardinality or weight constraints - like checking the consistency of a program - are intractable. Many intractable problems in the area of knowledge representation and reasoning have been shown to become linear time tractable if the treewidth of the programs or formulas under consideration is bounded by some constant. The goal of this paper is to apply the notion of treewidth to programs with cardinality or weight constraints and to identify tractable fragments. It will turn out that the straightforward application of treewidth to such class of programs does not suffice to obtain tractability. However, by imposing further restrictions, tractability can be achieved.

关键词： answer-set programming parameterized complexity analysis treewidth

来源：评论

学校读者我要写书评

暂无评论

A general framework for equivalences in answer-set programming by countermodels in the logic of Here-and-There

引用

THEORY AND PRACTICE OF LOGIC programming 2011年第2-3期11卷 171-202页

作者： Fink, Michael Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria

Different notions of equivalence, such as the prominent notions of strong and uniform equivalence, have been studied in answer-set programming, mainly for the purpose of identifying programs that can serve as substitutes without altering the semantics, for instance in program optimization. Such semantic comparisons are usually characterized by various selections of models in the logic of Here-and- There (HT). For uniform equivalence however, correct characterizations in terms of HT-models can only be obtained for finite theories, respectively programs. In this paper, we show that a selection of countermodels in HT captures uniform equivalence also for infinite theories. This result is turned into coherent characterizations of the different notions of equivalence by countermodels, as well as by a mixture of HT-models and countermodels (so-called equivalence interpretations). Moreover, we generalize the so-called notion of relativized hyperequivalence for programs to propositional theories, and apply the same methodology in order to obtain a semantic characterization which is amenable to infinite settings. This allows for a lifting of the results to first-order theories under a very general semantics given in terms of a quantified version of HT. We thus obtain a general framework for the study of various notions of equivalence for theories under answer-set semantics. Moreover, we prove an expedient property that allows for a simplified treatment of extended signatures, and provide further results for non-ground logic programs. In particular, uniform equivalence coincides under open and ordinary answer-set semantics, and for finite non-ground programs under these semantics, also the usual characterization of uniform equivalence in terms of maximal and total HT-models of the grounding is correct, even for infinite domains, when corresponding ground programs are infinite.

关键词： answer-set programming Uniform equivalence Relativized equivalence Knowledge representation

来源：评论

学校读者我要写书评

暂无评论

TOWARDS A GENERAL ARGUMENTATION SYSTEM BASED ON answer-set programming

TOWARDS A GENERAL ARGUMENTATION SYSTEM BASED ON ANSWER-SET P...

引用

26th International Conference on Logic programming (ICLP)

作者： Gaggl, Sarah Alice Vienna Univ Technol Inst Informat Syst 184 2 Favoritenstr 9-11 A-1040 Vienna Austria

ISBN: (纸本)9783939897170

Within the last years, especially since the work proposed by Dung in 1995, argumentation has emerged as a central issue in Artificial Intelligence. With the so called argumentation frameworks (AFs) it is possible to represent statements (arguments) together with a binary attack relation between them. The conflicts between the statements are solved on a semantical level by selecting acceptable sets of arguments. An increasing amount of data requires an automated computation of such solutions. Logic programming in particular answer-set programming (ASP) turned out to be adequate to solve problems associated to such AFs. In this work we use ASP to design a sophisticated system for the evaluation of several types of argumentation frameworks.

关键词： Argumentation Implementation answer-set programming

来源：评论

学校读者我要写书评

暂无评论

A Bird's-Eye View of Forgetting in answer-set programming 14th

A Bird's-Eye View of Forgetting in Answer-Set Programming

引用

14th International Conference on Logic programming and Nonmonotonic Reasoning (LPNMR)

作者： Leite, Joao Univ Nova Lisboa NOVA LINCS Lisbon Portugal Univ Nova Lisboa Dept Informat Lisbon Portugal

ISBN: (纸本)9783319616605;9783319616599

Forgetting is an operation that allows the removal, from a knowledge base, of middle variables no longer deemed relevant, while preserving all relationships (direct and indirect) between the remaining variables. When investigated in the context of answer-set programming, many different approaches to forgetting have been proposed, following different intuitions, and obeying different sets of properties. This talk will present a bird's-eye view of the complex landscape composed of the properties and operators of forgetting defined over the years in the context of answer-set programming, zooming in on recent findings triggered by the formulation of the so-called strong persistence, a property based on the strong equivalence between an answer-set program and the result of forgetting modulo the forgotten atoms, which seems to best encode the requirements of the forgetting operation.

关键词： Forgetting answer-set programming Variable elimination

来源：评论

学校读者我要写书评

暂无评论

ASPARTIX-V19-An answer-set programming Based System for Abstract Argumentation 1

引用

11th International Symposium on Foundations of Information and Knowledge Systems (FoIKS)

作者： Dvorak, Wolfgang Rapberger, Anna Wallner, Johannes P. Woltran, Stefan TU Wien Inst Log & Computat Vienna Austria

ISBN: (数字)9783030399511

ISBN: (纸本)9783030399511;9783030399504

We present ASPARTIX-V, a tool for reasoning in abstract argumentation frameworks that is based on answer-set programming (ASP), in its 2019 release. ASPARTIX-V participated in this year's edition of the International Competition on Computational Models of Argumentation (ICCMA'19) in all classical (static) reasoning tasks. In this paper we discuss extensions the ASPARTIX suite of systems has undergone for ICCMA'19. This includes incorporation of recent ASP language constructs (e.g. conditional literals), domain heuristics within ASP, and multi-shot methods. In particular, with this version of ASPARTIX-V we partially deviate from an earlier focus on monolithic approaches (i.e., one-shot solving via a single ASP encoding) to further enhance performance. We also briefly report on the results achieved by ASPARTIX-V in ICCMA'19.

关键词： Abstract argumentation Argumentation system answer-set programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：