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

On the generalization of learned constraints for ASP solving in temporal domains

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Romero, Javier Schaub, Torsten Strauch, Klaus University of Potsdam Germany

The representation of a temporal problem in ASP usually boils down to using copies of variables and constraints, one for each time stamp, no matter whether it is directly encoded or expressed via an action or temporal language. The multiplication of variables and constraints is commonly done during grounding and the solver is completely ignorant about the temporal relationship among the different instances. On the other hand, a key factor in the performance of today’s ASP solvers is conflict-driven constraint learning. Our question in this paper is whether a constraint learned for particular time steps can be generalized and reused at other time steps, and ultimately whether this enhances the overall solver performance on temporal problems. Knowing well the domain of time, we study conditions under which learned dynamic constraints can be generalized. Notably, we identify a property of temporal representations that enables the generalization of learned constraints across all time steps. It turns out that most ASP planning encodings either satisfy this property or can be easily adapted to do so. In addition, we propose a general translation that transforms programs to fulfill this property. Finally, we empirically evaluate the impact of adding the generalized constraints to an ASP solver. Under consideration in theory and practice of logic programming (TPLP) © 2024, CC BY.

关键词： logic programming

A concurrent constraint programming interpretation of access permissions

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Olarte, Carlos Pimentel, Elaine Rueda, Camilo ECT Universidade Federal Rio Grande do Norte Brazil DMAT Universidade Federal Rio Grande do Norte Brazil DECC Pontificia Universidad Javeriana Cali Colombia

A recent trend in object oriented (OO) programming languages is the use of Access Permissions (APs) as an abstraction for controlling concurrent executions of programs. The use of AP source code annotations defines a protocol specifying how object references can access the mutable state of objects. Although the use of APs simplifies the task of writing concurrent code, an unsystematic use of them can lead to subtle problems. This paper presents a declarative interpretation of APs as Linear Concurrent Constraint Programs (lcc). We represent APs as constraints (i.e., formulas in logic) in an underlying constraint system whose entailment relation models the transformation rules of APs. Moreover, we use processes in lcc to model the dependencies imposed by APs, thus allowing the faithful representation of their flow in the *** verify relevant properties about AP programs by taking advantage of the interpretation of lcc processes as formulas in Girard's intuitionistic linear logic (ILL). Properties include deadlock detection, program correctness (whether programs adhere to their AP specifications or not), and the ability of methods to run concurrently. By relying on a focusing discipline for ILL, we provide a complexity measure for proofs of the above mentioned properties. The effectiveness of our verification techniques is demonstrated by implementing the Alcove tool that includes an animator and a verifier. The former executes the lcc model, observing the flow of APs and quickly finding inconsistencies of the APs vis-á-vis the implementation. The latter is an automatic theorem prover based on ILL. This paper is under consideration for publication in theory and practice of logic programming (TPLP). Copyright © 2018, The Authors. All rights reserved.

关键词： Computer circuits

Temporal minimal-World semantics for sparse ABoxes

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Borgwardt, Stefan Forkel, Walter Kovtunova, Alisa Chair for Automata Theory Technische Universität Dresden Germany

Ontology-mediated query answering is a popular paradigm for enriching answers to user queries with background knowledge. For querying the absence of information, however, there exist only few ontology-based approaches. Moreover, these proposals conflate the closed-domain and closed-world assumption, and therefore are not suited to deal with the anonymous objects that are common in ontological reasoning. Many real-world applications, like processing electronic health records (EHRs), also contain a temporal dimension, and require efficient reasoning algorithms. Moreover, since medical data is not recorded on a regular basis, reasoners must deal with sparse data with potentially large temporal gaps. Our contribution consists of two main parts: In the first part we introduce a new closed-world semantics for answering conjunctive queries with negation over ontologies formulated in the description logic 'ELH⊥, which is based on the minimal canonical model. We propose a rewriting strategy for dealing with negated query atoms, which shows that query answering is possible in polynomial time in data complexity. In the second part, we extend this minimal-world semantics for answering metric temporal conjunctive queries with negation over the lightweight temporal logic 'Equation Presented' and obtain similar rewritability and complexity results. This paper is under consideration in theory and practice of logic programming (TPLP). Copyright © 2021, The Authors. All rights reserved.

关键词： Ontology

Answer-Set programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Eiter, Thomas Geibinger, Tobias Musliu, Nysret Oetsch, Johannes Skočovský, Peter Stepanova, Daria Austria Bosch Center for AI Robert Bosch Campus 1 RenningenD-71272 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 KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers. Under consideration in theory and practice of logic programming (TPLP). © 2022, CC BY.

关键词： Job shop scheduling

Constraining interference in an object-based design method 4th

学校读者我要写书评

暂无评论

4th International Joint Conference on the theory and practice of Software Development, TAPSOFT 1993

作者： Jones, C.B. Department of Computer Science Manchester University M13 9PL United Kingdom

ISBN: (纸本)9783540566106

This paper is the first of a series which are intended to contribute to tractable development methods for concurrent programs by exploring ways in which object-based language concepts can be used to provide a compositional development method for concurrent programs. The property of a (formal) development method which gives the development process the potential for productivity is compositionality;interference is what makes it difficult to find compositional development methods for concurrent systems. This paper shows how object-based concepts can be used to provide a designer with control over interference;it also proposes a transformational style of development (for systems with limited interference) in which concurrency is introduced only in the final stages of design. The essential idea here is to show that certain object graphs limit interference. A companion paper discusses the problems of interference more fully and shows how a suitable logic can be used to reason about those systems where interference plays an essential role. There again, concepts are used in the design notation which are taken from object-oriented languages since they offer control of granularity and way of pinpointing interference. A third paper is in preparation which defines the semantics of the object-based design notation. © Springer-Verlag Berlin Heidelberg 1993.

关键词： Object oriented programming

Operating room (Re)scheduling with bed management via ASP

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Dodaro, Carmine Galatà, Giuseppe Khan, Muhammad Kamran Maratea, Marco Porro, Ivan University of Calabria Italy SurgiQ srl Italy University of Genoa Italy

The Operating Room Scheduling (ORS) problem is the task of assigning patients to operating rooms, taking into account different specialties, lengths and priority scores of each planned surgery, operating room session durations, and the availability of beds for the entire length of stay both in the Intensive Care Unit and in the wards. A proper solution to the ORS problem is of primary importance for the healthcare service quality and the satisfaction of patients in hospital environments. In this paper we first present a solution to the problem based on Answer Set programming (ASP). The solution is tested on benchmarks with realistic sizes and parameters, on three scenarios for the target length on 5-day scheduling, common in small-medium sized hospitals, and results show that ASP is a suitable solving methodology for the ORS problem in such setting. Then, we also performed a scalability analysis on the schedule length up to 15 days, which still shows the suitability of our solution also on longer plan horizons. Moreover, we also present an ASP solution for the rescheduling problem, i.e. when the off-line schedule cannot be completed for some reason. Finally, we introduce a web framework for managing ORS problems via ASP that allows a user to insert the main parameters of the problem, solve a specific instance, and show results graphically in real-time. Under consideration in theory and practice of logic programming (TPLP).12. Copyright © 2021, The Authors. All rights reserved.

关键词： logic programming

Proving the Asymmetry Thesis Principles for a BDI Agent-Oriented programming Language

学校读者我要写书评

暂无评论

Electronic Notes in Theoretical Computer Science 2002年第5期70卷 108-125页

作者： Rafael H. Bordini Álvaro F. Moreira Departamento de Informática Teórica (INT) Instituto de Informática (II) Universidade Federal do Rio Grande do Sul (UFRGS) CP 15064 91501-970 Porto Alegre RS Brazil Departamento de Informática (DEIN) Centro de Ciências Exatas e Teccnologia (CCET) Universidade de Caxias do Sul (UCS) 95070-560 Caxias do Sul RS Brazil

In this paper, we consider each of the nine principles of BDI logics as defined by Rao and Georgeff based on Bratman's asymmetry thesis, and we verify which ones are satisfied by Rao's AgentSpeak(L), a computable logic language inspired by the BDI architecture for cognitive agents. This is in line with Rao's original motivation for defining AgentSpeak(L): to bridge the gap between the theory and practice of BDI agent systems. In order to set the grounds for the proof, we first introduce a particular way in which to define the informational, motivational, and deliberative modalities of BDI logics for AgentSpeak(L) agents, according to its structural operational semantics (that we introduced in a recent paper). This provides a framework that can be used to investigate further properties of AgentSpeak(L) agents, contributing towards giving firm theoretical grounds for BDI agent programming.

关键词：

Constraint answer set programming without grounding

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Arias, Joaquin Carro, Manuel Salazar, Elmer Marple, Kyle Gupta, Gopal IMDEA Software Institute Universidad Politécnica de Madrid University of Texas Dallas United States

Extending ASP with constraints (CASP) enhances its expressiveness and performance. This extension is not straightforward as the grounding phase, present in most ASP systems, removes variables and the links among them, and also causes a combinatorial explosion in the size of the program. Several methods to overcome this issue have been devised: restricting the constraint domains (e.g., discrete instead of dense), or the type (or number) of models that can be returned. In this paper we propose to incorporate constraints into s(ASP), a goal-directed, top-down execution model which implements ASP while retaining logical variables both during execution and in the answer sets. The resulting model, s(CASP), can constrain variables that, as in CLP, are kept during the execution and in the answer sets. s(CASP) inherits and generalizes the execution model of s(ASP) and is parametric w.r.t. the constraint solver. We describe this novel execution model and show through several examples the enhanced expressiveness of s(CASP) w.r.t. ASP, CLP, and other CASP systems. We also report improved performance w.r.t. other very mature, highly optimized ASP systems in some benchmarks. This paper is under consideration for publication in theory and practice of logic programming (TPLP). Copyright © 2018, The Authors. All rights reserved.

关键词： logic programming

A logic-based framework leveraging neural networks for studying the evolution of neurological disorders

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Calimeri, Francesco Cauteruccio, Francesco Cinelli, Luca Marzullo, Aldo Stamile, Claudio Terracina, Giorgio Durand-Dubief, Françoise Sappey-Marinier, Dominique DEMACS University of Calabria Italy CREATIS CNRS UMR 5220 INSERM U1206 Université de Lyon Université Lyon 1 INSA-Lyon Villeurbanne France Hôpital Neurologique Service de Neurologie A Hospices Civils de Lyon Bron France CERMEP - Imagerie du Vivant Université de Lyon Bron France

Deductive formalisms have been strongly developed in recent years;among them, Answer Set programming (ASP) gained some momentum, and has been lately fruitfully employed in many real-world scenarios. Nonetheless, in spite of a large number of success stories in relevant application areas, and even in industrial contexts, deductive reasoning cannot be considered the ultimate, comprehensive solution to AI;indeed, in several contexts, other approaches result to be more useful. Typical Bioinformatics tasks, for instance classification, are currently carried out mostly by Machine Learning (ML) based solutions. In this paper, we focus on the relatively new problem of analyzing the evolution of neurological disorders. In this context, ML approaches already demonstrated to be a viable solution for classification tasks;here, we show how ASP can play a relevant role in the brain evolution simulation task. In particular, we propose a general and extensible framework to support physicians and researchers at understanding the complex mechanisms underlying neurological disorders. The framework relies on a combined use of ML and ASP, and is general enough to be applied in several other application scenarios, which are outlined in the paper. Under consideration in theory and practice of logic programming (TPLP). Copyright © 2019, The Authors. All rights reserved.

关键词： logic programming