We propose an interpretation of the first-order answer set programming (FOASP) in terms of intuitionistic proof theory. It is obtained by two polynomial translations between FOASP and the bounded-arity fragment of the...
详细信息
We propose an interpretation of the first-order answer set programming (FOASP) in terms of intuitionistic proof theory. It is obtained by two polynomial translations between FOASP and the bounded-arity fragment of the Sigma(1) level of the Mints hierarchy in first-order intuitionistic logic. It follows that Sigma(1) formulas using predicates of fixed arity (in particular unary) is of the same strength as FOASP. Our construction reveals a close similarity between constructive provability and stable entailment, or equivalently, between the construction of an answerset and an intuitionistic refutation. This paper is under consideration for publication in Theory and Practice of Logic programming.
We study finding similar or diverse solutions of a given computational problem, in answer set programming, and introduce offline methods and online methods to compute them using answerset solvers. We analyze the comp...
详细信息
ISBN:
(纸本)9783642028458
We study finding similar or diverse solutions of a given computational problem, in answer set programming, and introduce offline methods and online methods to compute them using answerset solvers. We analyze the computational complexity of some problems that are related to finding similar or diverse solutions, and show the applicability and effectiveness of our methods in phylogeny reconstruction.
answer set programming (ASP) is a declarative language for nonmonotonic reasoning based on stable model semantics. Astable model is a classical model of the input program satisfying the following stability condition: ...
详细信息
answer set programming (ASP) is a declarative language for nonmonotonic reasoning based on stable model semantics. Astable model is a classical model of the input program satisfying the following stability condition: only necessary information is included in the model under the assumptions provided by the model itself for the unknown knowledge in the program, where unknown knowledge is encoded by means of default negation. Rational agents acting in the real world often have to reason in presence of unknown knowledge. It is also common that real world agents cannot meet all their desiderata. For this reason, ASP programs may include weak constraints for representing numerical preferences over jointly incompatible conditions. Stable models are therefore associated with a cost given by the unsatisfied weak constraints, and stable models of minimum cost are preferred. This paper summarizes algorithms and strategies for computing optimal stable models, and hints on how these algorithms can be extended to handle some qualitative preferences that have a natural representation in circumscription, that is, those based on subset-minimality and superset-maximality.
answer set programming (ASP) is a declarative programming paradigm which allows for easy modeling and solving of hard problems that are often cumbersome to implement in object-oriented programming languages. It was su...
详细信息
ISBN:
(纸本)9783319516769;9783319516752
answer set programming (ASP) is a declarative programming paradigm which allows for easy modeling and solving of hard problems that are often cumbersome to implement in object-oriented programming languages. It was successfully applied to a range of applications from artificial intelligence, such as combinatorial or scheduling problems. On the other hand, real-world applications for end-users usually consist also of components which cannot be (easily) solved in ASP, such as user interaction via graphical user interfaces, presentation of results, and interfaces to data sources. Instead, realizing such components is typically in the domain of traditional (object-oriented) programming languages. To address this issue, we introduce a language which allows for a formal specification of the input and output of an ASP program, which can be exploited to easily interface the program from object-oriented languages using a dedicated library. While the language is independent from the concrete object-oriented language, we also provide and present a reference implementation as a Python library. We then discuss some applications which can be realized on top of our approach.
answer set programming (ASP) is a well-established logic programming language that offers an intuitive, declarative syntax for problem solving. In its traditional application, a fixed ASP program for a given problem i...
详细信息
answer set programming (ASP) is a well-established logic programming language that offers an intuitive, declarative syntax for problem solving. In its traditional application, a fixed ASP program for a given problem is designed and the actual instance of the problem is fed into the program as a set of facts. This approach typically results in programs with comparably short and simple rules. However, as is known from complexity analysis, such an approach limits the expressive power of ASP;in fact, an entire NP-check can be encoded into a single large rule body of bounded arity that performs both a guess and a check within the same rule. Here, we propose a novel paradigm for encoding hard problems in ASP by making explicit use of large rules which depend on the actual instance of the problem. We illustrate how this new encoding paradigm can be used, providing examples of problems from the first, second, and even third level of the polynomial hierarchy. As state-of-the-art solvers are tuned towards short rules, rule decomposition is a key technique in the practical realization of our approach. We also provide some preliminary benchmarks which indicate that giving up the convenient way of specifying a fixed program can lead to a significant speed-up.
We present xclingo, a tool for generating explanations from ASP programs annotated with text and labels. These annotations allow tracing the application of rules or the atoms derived by them. The input of xclingo is a...
详细信息
We present xclingo, a tool for generating explanations from ASP programs annotated with text and labels. These annotations allow tracing the application of rules or the atoms derived by them. The input of xclingo is a markup language written as ASP comment lines, so the programs annotated in this way can still be accepted by a standard ASP solver. xclingo translates the annotations into additional predicates and rules and uses the ASP solver clingo to obtain the extension of those auxiliary predicates. This information is used afterwards to construct derivation trees containing textual explanations. The language allows selecting which atoms to explain and, in its turn, which atoms or rules to include in those explanations. We illustrate the basic features through a diagnosis problem from the literature.
Points-to information is essential in software engineering, including compiler optimization, instruction-level parallelism, program verification, and so on. The propagating of points-to information along paths of a pr...
详细信息
ISBN:
(纸本)9783642247279
Points-to information is essential in software engineering, including compiler optimization, instruction-level parallelism, program verification, and so on. The propagating of points-to information along paths of a program can be viewed as the "frame problem" in a dynamic world. As a primary knowledge representing and reasoning tool in Artificial Intelligence, answer set programming (ASP) provides a natural and concise way to express the frame problem. We present a collection of ASP rules to model the propagating of points-to information along paths of an object-oriented program. With these rules and basic facts of a program. points-to information at each program point can be computed easily. This makes it possible to acquire useful information for program analysis through existing ASP solvers.
Course scheduling or timetabling is a well-known problem that is generally studied from the perspective of schools;the goal is to schedule the courses, considering, e.g., the expected number of students, the sizes of ...
详细信息
ISBN:
(纸本)9783030059989;9783030059972
Course scheduling or timetabling is a well-known problem that is generally studied from the perspective of schools;the goal is to schedule the courses, considering, e.g., the expected number of students, the sizes of the available classrooms, time conflicts between courses of the same category. We study a complementary problem to help the students during the course registration periods;the goal is to plan personalized course schedules for students, considering, e.g., their preferences over sections, instructors, distribution of the courses. We present a declarative method to compute personalized course schedules, and an application of this method using answer set programming, and discuss promising results of some preliminary user evaluations via surveys.
answer set programming (ASP) is a new programming language paradigm combining the declarative aspect with non-monotonic reasoning. In this paper, we will investigate and evaluate an application of Simple Assembly Line...
详细信息
ISBN:
(纸本)9781509055104
answer set programming (ASP) is a new programming language paradigm combining the declarative aspect with non-monotonic reasoning. In this paper, we will investigate and evaluate an application of Simple Assembly Line Balancing Problem in answer set programming. The problem is a highly combinatorial and is generally solved by specific programs. We present an approach to solve the simple assembly line balancing problem in answer set programming and compare them with the standard ones. It turns out that, although answer set programming greatly simplifies the problem statement. It is comparable in efficiency to specialized programs.
In this paper, we propose a formal framework for checking the consistency of security policies of services using answer set programming (ASP). We illustrate that the formalisation of security policies of the service p...
详细信息
ISBN:
(纸本)9781479950669
In this paper, we propose a formal framework for checking the consistency of security policies of services using answer set programming (ASP). We illustrate that the formalisation of security policies of the service providers and the service consumers in ASP is an effective way for reasoning about the compatibility of policies to enable the dynamic discovery and invocation of services.
暂无评论