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

Treewidth-aware reductions of normal ASP to SAT - Is normal ASP harder than SAT after all?

ARTIFICIAL INTELLIGENCE 2022年 304卷 103651-103651页

作者： Hecher, Markus TU Wien Favoritenstr 9-11 A-1040 Vienna Austria Univ Potsdam Neuen Palais 10 D-14469 Potsdam Germany

answer set programming (ASP) is a paradigm for modeling and solving problems for knowledge representation and reasoning. There are plenty of results dedicated to studying the hardness of (fragments of) ASP. So far, these studies resulted in characterizations in terms of computational complexity as well as in fine-grained insights presented in form of dichotomy-style results, lower bounds when translating to other formalisms like propositional satisfiability (SAT), and even detailed parameterized complexity landscapes. A generic parameter in parameterized complexity originating from graph theory is the socalled treewidth, which in a sense captures structural density of a program. Recently, there was an increase in the number of treewidth-based solvers related to SAT. While there are translations from (normal) ASP to SAT, no reduction that preserves treewidth or at least keeps track of the treewidth increase is known. In this paper we propose a novel reduction from normal ASP to SAT that is aware of the treewidth, and guarantees that a slight increase of treewidth is indeed sufficient. Further, we show a new result establishing that, when considering treewidth, already the fragment of normal ASP is slightly harder than SAT (under reasonable assumptions in computational complexity). This also confirms that our reduction probably cannot be significantly improved and that the slight increase of treewidth is unavoidable. Finally, we present an empirical study of our novel reduction from normal ASP to SAT, where we compare treewidth upper bounds that are obtained via known decomposition heuristics. Overall, our reduction works better with these heuristics than existing translations. (c) 2021 Elsevier B.V. All rights reserved.

关键词： answer set programming Treewidth Parameterized complexity Complexity analysis Tree decomposition Treewidth-aware reductions

来源：评论

学校读者我要写书评

暂无评论

Comparing the Reasoning Capabilities of Equilibrium Theories and answer set Programs

引用

ALGORITHMS 2022年第6期15卷 201-201页

作者： Fandinno, Jorge Pearce, David Vidal, Concepcion Woltran, Stefan Univ Nebraska Coll Informat Sci & Technol 6001 Dodge St Omaha NE 68182 USA Univ Politecn Madrid Dept Inteligencia Artificial Madrid 28040 Spain Univ A Coruna Comp Sci & Informat Technol La Coruna 15008 Spain Tech Univ Wien Databases & Artificial Intelligence Grp E192 02 Inst Log & Computat A-1040 Vienna Austria

answer set programming (ASP) is a well established logical approach in artificial intelligence that is widely used for knowledge representation and problem solving. Equilibrium logic extends answer set semantics to more general classes of programs and theories. When intertheory relations are studied in ASP, or in the more general form of equilibrium logic, they are usually understood in the form of comparisons of the answer sets or equilibrium models of theories or programs. This is the case for strong and uniform equivalence and their relativised and projective versions. However, there are many potential areas of application of ASP for which query answering is relevant and a comparison of programs in terms of what can be inferred from them may be important. We formulate and study some natural equivalence and entailment concepts for programs and theories that are couched in terms of inference and query answering. We show that, for the most part, these new intertheory relations coincide with their model-theoretic counterparts. We also extend some previous results on projective entailment for theories and for the new connective called fork.

关键词： answer set programming equilibrium logic intertheory relations projective entailment forks in ASP

来源：评论

学校读者我要写书评

暂无评论

Temporal equilibrium logic: a survey

引用

Journal of Applied Non-Classical Logics 2013年第1-2期23卷 2-24页

This paper contains a survey of the main definitions and results obtained to date related to Temporal Equilibrium Logic, a nonmonotonic hybrid approach that combines Equilibrium Logic (the best-known logical character... 详细信息

关键词： answer set programming linear temporal logic equilibrium logic nonmonotonic reasoning knowledge representation

来源：评论

学校读者我要写书评

暂无评论

Pushing the Limits of Clingo's Incremental Grounding and Solving Capabilities in Practical Applications

引用

ALGORITHMS 2023年第3期16卷 169-169页

作者： Balduccini, Marcello Barborak, Michael Ferrucci, David Elemental Cognit Inc New York NY 10169 USA St Josephs Univ Dept Decis & Syst Sci Erivan K Haub Sch Business Philadelphia PA 19131 USA

Incremental techniques aim at making it possible to improve the performance of the grounding and solving processes by reusing the results of previous executions. Clingo supports both incremental grounding and incremental solving computations. In order to leverage incremental computations in clingo, the incremental fragments of ASP programs must satisfy certain safety-related conditions. In a number of problem domains and reasoning tasks, these conditions can be satisfied in a fairly straightforward way. However, we have observed that in certain practical applications, satisfying the conditions becomes more challenging, to the point that it is sometimes unclear how or even if it is possible to leverage incremental computations. In this paper, we report our findings, and ultimate success, with the use of incremental grounding and solving techniques in one of these challenging cases. We describe the domain, which is linked to a large practical application, discuss the challenges we faced in attempting to leverage incremental computations, and then describe the techniques that we developed, in particular at the level of methods for encoding the domain knowledge and of algorithms supporting the intended interleaving of grounding and solving. We believe that our findings may provide valuable information to practitioners facing similar challenges and ultimately increase the adoption of clingo's incremental capabilities for complex practical applications.

关键词： answer set programming multi-shot solving durative actions durative fluents reasoning about actions and change

来源：评论

学校读者我要写书评

暂无评论

ASP-Based Declarative Reasoning in Data-Intensive Enterprise and IoT Applications

引用

ALGORITHMS 2023年第3期16卷 159-159页

作者： Calimeri, Francesco Leone, Nicola Melissari, Giovanni Pacenza, Francesco Perri, Simona Reale, Kristian Ricca, Francesco Zangari, Jessica Univ Calabria Dept Math & Comp Sci I-87036 Arcavacata Di Rende Italy DLVSystem LTD Via Resistenza 19-C I-87036 Arcavacata Di Rende Italy

In the last few years, we have witnessed the spread of computing devices getting smaller and smaller (e.g., Smartphones, Smart Devices, Raspberry, etc.), and the production and availability of data getting bigger and bigger. This work presents DLV-EE, a framework based on answer set programming (ASP) for performing declarative reasoning tasks over data-intensive, distributed applications. It relies on the DLV2 system and it features interoperability means for dealing with Big-Data over modern industry-level databases (relational and NoSQL). Furthermore, the work introduces DLV-IoT, an ASP system compatible with "mobile" technologies for enabling advanced reasoning capabilities on smart/IoT devices;eventually, DLV-EE and DLV-IoT via some real-world applications are illustrated as well.

关键词： answer set programming Non-monotonic Reasoning DLV Big Data SQL NoSQL IoT Raspberry Android

来源：评论

学校读者我要写书评

暂无评论

Event-Based and Scenario-Based Causality for Computational Ethics 18

Event-Based and Scenario-Based Causality for Computational E...

引用

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

作者： Fiona Berreby Gauvain Bourgne Jean-Gabriel Ganascia Sorbonne Université-CNRS Paris France

This paper makes use of high-level action languages to investigate aspects of causality that are central to ethical reasoning. We identify properties that causal relations assume and that determine how, as well as to what extent, we may ascribe ethical responsibility on their basis. The paper is structured in three parts. First, we present an extension of the Event Calculus that enables the agent to generate plans of actions, with the particularity that they integrate both actions and omissions. Second, we present an account of event-based causality that is grounded in the architecture of event preconditions and effects, and that distinguishes four types of causal relations contingent on the nature of the entities that compose them. Namely, it discriminates actions and omissions from automatic events, and produced outcomes from avoided ones. Third, we examine notions of scenario-based causality whose role it is to scrutinise and buttress the causal relations previously identified. Inquiring into the other possible versions of modelled scenarios, we account for simple counter-factual validity ("Had I not acted so, would this outcome still be true?"), criticality ("Could anything else have led to this outcome?"), extrinsic necessity ("Had I not produced it, was this outcome even avoidable?"), and elicited necessity ("Have I made this outcome unavoidable?"). The model is implemented in answer set programming.

关键词： event calculus answer set programming causality reasoning about actions and change counter-factuals computational ethics

来源：评论

学校读者我要写书评

暂无评论

On the decidability of FDNC programs

引用

INTELLIGENZA ARTIFICIALE 2011年第1期5卷 89-93页

作者： Bonatti, Piero A. Univ Naples Federico II Dept Phys Via Cinthia I-80126 Naples Italy

We provide a new decidability proof for the consistency of FDNC programs under the stable model semantics, based on regular splitting sequences. With this technique, we can slightly relax the definition of FDNC programs and make a first step towards a precise understanding of the relationships between FDNC programs and finitely recursive programs.

关键词： answer set programming finitely recursive finitary and FDNC programs module sequences

来源：评论

学校读者我要写书评

暂无评论

A Neuro-Symbolic Approach for Fault Diagnosis in Smart Power Grids 22

A Neuro-Symbolic Approach for Fault Diagnosis in Smart Power...

引用

Proceedings of the 26th Pan-Hellenic Conference on Informatics

作者： Theofanis Aravanis Ioannis Kabouris University of the Peloponnese Greece and University of Patras Greece University of the Peloponnese Greece

ISBN: (纸本)9781450398541

Power quality is a critical parameter of modern power electrical systems, the complexity and decentralization of which are rapidly increasing. Indeed, the highest possible quality is a requirement of all the stakeholders of a power grid. In response to this demand, we introduce, in this article, a novel neuro-symbolic approach for the diagnosis (i.e., detection and classification) of the typical faults that a smart power grid encounters during its operation (that is, voltage interruptions, voltage sags, voltage swells, transients and harmonics). Heart of the implemented system is an Artificial Neural Network (ANN) that identifies with high fidelity the patterns of voltage-waveforms — for the sake of comparison, two ANNs were evaluated, namely, a conventional Multilayer Perceptron (MLP) and a one-dimensional Convolutional Neural Network (CNN). The output of the ANN is passed through a symbolic reasoner, implemented by means of answer set programming (ASP), which provides a final response on the condition of the power grid, taking into account the background knowledge of the domain, which is in turn encoded into appropriate symbolic rules. The proposed approach achieved very high classification-performance on the validation dataset ( the MLP and the CNN), and, thus, it constitutes a promising powerful tool that will contribute to the improved quality of future power grids.

关键词： Power Electrical Systems Fault Diagnosis answer set programming Smart Grids Neuro-Symbolic Artificial Intelligence Artificial Neural Networks Convolutional Neural Networks

来源：评论

学校读者我要写书评

暂无评论

On the Semantics of Hybrid ASP Systems Based on Clingo

引用

ALGORITHMS 2023年第4期16卷 185-185页

作者： Cabalar, Pedro Fandinno, Jorge Schaub, Torsten Wanko, Philipp Univ A Coruna Dept Comp Sci A Corunna 15008 Spain Univ Nebraska Omaha Coll Informat Sci & Technol Omaha NE 68182 USA Univ Potsdam Dept Comp Sci D-14469 Potsdam Germany

Over the last decades, the development of answer set programming (ASP) has brought about an expressive modeling language powered by highly performant systems. At the same time, it gets more and more difficult to provide semantic underpinnings capturing the resulting constructs and inferences. This is even more severe when it comes to hybrid ASP languages and systems that are often needed to handle real-world applications. We address this challenge and introduce the concept of abstract and structured theories that allow us to formally elaborate upon their integration with ASP. We then use this concept to make the semantic characterization of clingo's theory-reasoning framework precise. This provides us with a formal framework in which we can elaborate upon the formal properties of existing hybridizations of clingo, such as clingcon, clingo[dl], and clingo[lp].

关键词： answer set programming answer set programming modulo theories hybrid reasoning semantic foundations

来源：评论

学校读者我要写书评

暂无评论

Constraints On Signaling Networks Logic Reveal Functional Subgraphs On Multiple Myeloma OMIC Data 17

Constraints On Signaling Networks Logic Reveal Functional Su...

引用

Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology,and Health Informatics

作者： Bertrand Miannay Stéphane Minvielle Olivier Roux Florence Magrangeas Carito Guziolowski LS2N UMR 6004 Ecole Centrale de Nantes Nantes France CRCINA INSERM CNRS Université d'AngersUniversité de Nantes Nantes France

ISBN: (纸本)9781450347228

The integration of gene expression profiles (GEPs) and large-scale biological networks derived from Pathways Databases is a subject which is being widely explored. Existing methods are based on network distance measures among significantly measured species. Only a small number of them include the directionality and underlying logic existing in biological networks. In this study we approach the GEP-networks integration problem by considering the network logic but our approach does not require a prior species selection according to their gene expression level. We start by modeling the biological network representing its underlying logic using Logic programming. This model points to reachable network discrete states that maximize a notion of harmony between the molecular species active or inactive possible states and the directionality of the pathways reactions according to their activator or inhibitor control role. Only then, we confront these network states with the GEP. From this analysis independent graph components are derived, each of them related to a fixed and optimal assignment of active or inactive states. These components allow us to decompose a large-scale network into subgraphs and their molecular species state assignments have different degrees of similarity when compared to the same GEP. We applied our method to study the set of possible states derived from a subgraph from the NCI-PID Pathway Interaction Database. This graph linked Multiple Myeloma (MM) genes to known receptors for this blood cancer.

关键词： omic data integration answer set programming regulatory network modeling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：