The Experts below are selected from a list of 11343 Experts worldwide ranked by ideXlab platform
Miroslaw Truszczynski - One of the best experts on this subject based on the ideXlab platform.
-
The Informal Semantics of Answer Set Programming: A Tarskian Perspective
arXiv: Artificial Intelligence, 2019Co-Authors: Marc Denecker, Yuliya Lierler, Miroslaw Truszczynski, Joost VennekensAbstract:In Knowledge Representation, it is crucial that knowledge engineers have a good understanding of the formal expressions that they write. What formal expressions state intuitively about the domain of discourse is studied in the theory of the informal semantics of a logic. In this paper we study the informal semantics of Answer Set Programming. The roots of Answer Set Programming lie in the language of Extended Logic Programming, which was introduced initially as an epistemic logic for default and autoepistemic reasoning. In 1999, the seminal papers on Answer Set Programming proposed to use this logic for a different purpose, namely, to model and solve search problems. Currently, the language is used primarily in this new role. However, the original epistemic intuitions lose their explanatory relevance in this new context. How Answer Set programs are connected to the specifications of problems they model is more easily explained in a classical Tarskian semantics, in which models correspond to possible worlds, rather than to belief states of an epistemic agent. In this paper, we develop a new theory of the informal semantics of Answer Set Programming, which is formulated in the Tarskian Setting and based on Frege's compositionality principle. It differs substantially from the earlier epistemic theory of informal semantics, providing a different view on the meaning of the connectives in Answer Set Programming and on its relation to other logics, in particular classical logic.
-
Answer Set Programming: An Introduction to the Special Issue
AI Magazine, 2016Co-Authors: Gerhard Brewka, Thomas Eiter, Miroslaw TruszczynskiAbstract:This editorial introduces Answer Set Programming, a vibrant research area in computational knowledge representation and declarative Programming. We give a brief overview of the articles that form this special issue on Answer Set Programming and of the main topics they discuss.
-
Answer Set Programming at a glance
Communications of the ACM, 2011Co-Authors: Gerhard Brewka, Thomas Eiter, Miroslaw TruszczynskiAbstract:The motivation and key concepts behind Answer Set Programming---a promising approach to declarative problem solving.
-
the second Answer Set Programming competition
International Conference on Logic Programming, 2009Co-Authors: Marc Denecker, Martin Gebser, Joost Vennekens, Stephen Bond, Miroslaw TruszczynskiAbstract:This paper reports on the Second Answer Set Programming Competition . The competitions in areas of Satisfiability checking, Pseudo-Boolean constraint solving and Quantified Boolean Formula evaluation have proven to be a strong driving force for a community to develop better performing systems. Following this experience, the Answer Set Programming competition series was Set up in 2007, and ran as part of the International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR). This second competition, held in conjunction with LPNMR 2009, differed from the first one in two important ways. First, while the original competition was restricted to systems designed for the Answer Set Programming language , the sequel was open to systems designed for other modeling languages, as well. Consequently, among the contestants of the second competition were a CLP(FD) team and three model generation systems for (extensions of) classical logic. Second, this latest competition covered not only satisfiability problems but also optimization ones. We present and discuss the Set-up and the results of the competition.
-
LPNMR - The Second Answer Set Programming Competition
Logic Programming and Nonmonotonic Reasoning, 2009Co-Authors: Marc Denecker, Martin Gebser, Joost Vennekens, Stephen Bond, Miroslaw TruszczynskiAbstract:This paper reports on the Second Answer Set Programming Competition . The competitions in areas of Satisfiability checking, Pseudo-Boolean constraint solving and Quantified Boolean Formula evaluation have proven to be a strong driving force for a community to develop better performing systems. Following this experience, the Answer Set Programming competition series was Set up in 2007, and ran as part of the International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR). This second competition, held in conjunction with LPNMR 2009, differed from the first one in two important ways. First, while the original competition was restricted to systems designed for the Answer Set Programming language , the sequel was open to systems designed for other modeling languages, as well. Consequently, among the contestants of the second competition were a CLP(FD) team and three model generation systems for (extensions of) classical logic. Second, this latest competition covered not only satisfiability problems but also optimization ones. We present and discuss the Set-up and the results of the competition.
Torsten Schaub - One of the best experts on this subject based on the ideXlab platform.
-
Answer Set Programming unleashed!
KI - Künstliche Intelligenz, 2018Co-Authors: Torsten Schaub, Stefan WoltranAbstract:Answer Set Programming faces an increasing popularity for problem solving in various domains. While its modeling language allows us to express many complex problems in an easy way, its solving technology enables their effective resolution. In what follows, we detail some of the key factors of its success. Answer Set Programming [ASP; Brewka et al. Commun ACM 54(12):92–103, (2011)] is seeing a rapid proliferation in academia and industry due to its easy and flexible way to model and solve knowledge-intense combinatorial (optimization) problems. To this end, ASP offers a high-level modeling language paired with high-performance solving technology. As a result, ASP systems provide out-off-the-box, general-purpose search engines that allow for enumerating (optimal) solutions. They are represented as Answer Sets, each being a Set of atoms representing a solution. The declarative approach of ASP allows a user to concentrate on a problem’s specification rather than the computational means to solve it. This makes ASP a prime candidate for rapid prototyping and an attractive tool for teaching key AI techniques since complex problems can be expressed in a succinct and elaboration tolerant way. This is eased by the tuning of ASP’s modeling language to knowledge representation and reasoning (KRR). The resulting impact is nicely reflected by a growing range of successful applications of ASP [Erdem et al. AI Mag 37(3):53–68, 2016; Falkner et al. Industrial applications of Answer Set Programming. K++nstliche Intelligenz (2018)].
-
Design Space Exploration with Answer Set Programming
Künstliche Intelligenz, 2018Co-Authors: Christian Haubelt, Kai Neubauer, Torsten Schaub, Philipp WankoAbstract:The aim of our project design space exploration with Answer Set Programming is to develop a general framework based on Answer Set Programming (ASP) that finds valid solutions to the system design problem and simultaneously performs Design Space Exploration (DSE) to find the most favorable alternatives. We leverage recent developments in ASP solving that allow for tight integration of background theories to create a holistic framework for effective DSE.
-
Temporal Answer Set Programming on Finite Traces
arXiv: Artificial Intelligence, 2018Co-Authors: Pedro Cabalar, Torsten Schaub, Roland Kaminski, Anna SchuhmannAbstract:In this paper, we introduce an alternative approach to Temporal Answer Set Programming that relies on a variation of Temporal Equilibrium Logic (TEL) for finite traces. This approach allows us to even out the expressiveness of TEL over infinite traces with the computational capacity of (incremental) Answer Set Programming (ASP). Also, we argue that finite traces are more natural when reasoning about action and change. As a result, our approach is readily implementable via multi-shot ASP systems and benefits from an extension of ASP's full-fledged input language with temporal operators. This includes future as well as past operators whose combination offers a rich temporal modeling language. For computation, we identify the class of temporal logic programs and prove that it constitutes a normal form for our approach. Finally, we outline two implementations, a generic one and an extension of clingo.
-
Grounding and Solving in Answer Set Programming
AI Magazine, 2016Co-Authors: Benjamin Kaufmann, Nicola Leone, Simona Perri, Torsten SchaubAbstract:Answer Set Programming is a declarative problem solving paradigm that rests upon a workflow involving modeling, grounding, and solving. While the former is described by Gebser and Schaub (2016), we focus here on key issues in grounding, or how to systematically replace object variables by ground terms in a effective way, and solving, or how to compute the Answer Sets of a propositional logic program obtained by grounding.
-
Answer Set Programming modulo Acyclicity
2015Co-Authors: Jori Bomanson, Martin Gebser, Toni Janhunen, Benjamin Kaufmann, Torsten SchaubAbstract:Acyclicity constraints are prevalent in knowledge representation and, in particular, applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the Answer Set Programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich Set of primitives to express constraints related with recursive structures. The implementation, obtained as an extension to the state-of-the-art Answer Set solver clasp, provides a unique combination of traditional unfounded Set checking with acyclicity propagation.
Martin Gebser - One of the best experts on this subject based on the ideXlab platform.
-
Answer Set Programming modulo Acyclicity
2015Co-Authors: Jori Bomanson, Martin Gebser, Toni Janhunen, Benjamin Kaufmann, Torsten SchaubAbstract:Acyclicity constraints are prevalent in knowledge representation and, in particular, applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the Answer Set Programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich Set of primitives to express constraints related with recursive structures. The implementation, obtained as an extension to the state-of-the-art Answer Set solver clasp, provides a unique combination of traditional unfounded Set checking with acyclicity propagation.
-
Shift-design with Answer Set Programming
2015Co-Authors: Michael Abseher, Torsten Schaub, Martin Gebser, Nysret Musliu, Stefan WoltranAbstract:Answer Set Programming (ASP) is a powerful declarative Programming paradigm that has been successfully applied to many dierent domains. Recently, ASP has also proved successful for hard optimization problems like course timetabling. In this paper, we approach another important task, namely, the shift design problem, aiming at an alignment of a minimum number of shifts in order to meet required numbers of employees (which typically vary for different time periods) in such a way that over- and understang is minimized. We provide an ASP encoding of the shift design problem, which, to the best of our knowledge, has not been addressed by ASP yet.
-
A System for Interactive Query Answering with Answer Set Programming
arXiv: Artificial Intelligence, 2013Co-Authors: Martin Gebser, Philipp Obermeier, Torsten SchaubAbstract:Reactive Answer Set Programming has paved the way for incorporating online information into operative solving processes. Although this technology was originally devised for dealing with data streams in dynamic environments, like assisted living and cognitive robotics, it can likewise be used to incorporate facts, rules, or queries provided by a user. As a result, we present the design and implementation of a system for interactive query Answering with reactive Answer Set Programming. Our system quontroller is based on the reactive solver oclingo and implemented as a dedicated front-end. We describe its functionality and implementation, and we illustrate its features by some selected use cases.
-
Answer Set Programming for Stream Reasoning
arXiv: Artificial Intelligence, 2013Co-Authors: Martin Gebser, Philipp Obermeier, Torsten Grote, Roland Kaminski, Orkunt Sabuncu, Torsten SchaubAbstract:The advance of Internet and Sensor technology has brought about new challenges evoked by the emergence of continuous data streams. Beyond rapid data processing, application areas like ambient assisted living, robotics, or dynamic scheduling involve complex reasoning tasks. We address such scenarios and elaborate upon approaches to knowledge-intense stream reasoning, based on Answer Set Programming (ASP). While traditional ASP methods are devised for singular problem solving, we develop new techniques to formulate and process problems dealing with emerging as well as expiring data in a seamless way.
-
LPNMR - Matchmaking with Answer Set Programming
Logic Programming and Nonmonotonic Reasoning, 2013Co-Authors: Martin Gebser, Orkunt Sabuncu, Thomas Glase, Torsten SchaubAbstract:Matchmaking is a form of scheduling that aims at bringing companies or people together that share common interests, services, or products in order to facilitate future business partnerships.We begin by furnishing a formal characterization of the corresponding multi-criteria optimization problem.We then address this problem by Answer Set Programming in order to solve real-world matchmaking instances, which were previously dealt with by special-purpose algorithms.
Yuliya Lierler - One of the best experts on this subject based on the ideXlab platform.
-
The Informal Semantics of Answer Set Programming: A Tarskian Perspective
arXiv: Artificial Intelligence, 2019Co-Authors: Marc Denecker, Yuliya Lierler, Miroslaw Truszczynski, Joost VennekensAbstract:In Knowledge Representation, it is crucial that knowledge engineers have a good understanding of the formal expressions that they write. What formal expressions state intuitively about the domain of discourse is studied in the theory of the informal semantics of a logic. In this paper we study the informal semantics of Answer Set Programming. The roots of Answer Set Programming lie in the language of Extended Logic Programming, which was introduced initially as an epistemic logic for default and autoepistemic reasoning. In 1999, the seminal papers on Answer Set Programming proposed to use this logic for a different purpose, namely, to model and solve search problems. Currently, the language is used primarily in this new role. However, the original epistemic intuitions lose their explanatory relevance in this new context. How Answer Set programs are connected to the specifications of problems they model is more easily explained in a classical Tarskian semantics, in which models correspond to possible worlds, rather than to belief states of an epistemic agent. In this paper, we develop a new theory of the informal semantics of Answer Set Programming, which is formulated in the Tarskian Setting and based on Frege's compositionality principle. It differs substantially from the earlier epistemic theory of informal semantics, providing a different view on the meaning of the connectives in Answer Set Programming and on its relation to other logics, in particular classical logic.
-
What is Answer Set Programming to propositional satisfiability
Constraints, 2017Co-Authors: Yuliya LierlerAbstract:Propositional satisfiability (or satisfiability) and Answer Set Programming are two closely related subareas of Artificial Intelligence that are used to model and solve difficult combinatorial search problems. Satisfiability solvers and Answer Set solvers are the software systems that find satisfying interpretations and Answer Sets for given propositional formulas and logic programs, respectively. These systems are closely related in their common design patterns. In satisfiability, a propositional formula is used to encode problem specifications in a way that its satisfying interpretations correspond to the solutions of the problem. To find solutions to a problem it is then sufficient to use a satisfiability solver on a corresponding formula. Niemelä, Marek, and Truszczyński coined Answer Set Programming paradigm in 1999: in this paradigm a logic program encodes problem specifications in a way that the Answer Sets of a logic program represent the solutions of the problem. As a result, to find solutions to a problem it is sufficient to use an Answer Set solver on a corresponding program. These parallels that we just draw between paradigms naturally bring up a question: what is a fundamental difference between the two? This paper takes a close look at this question.
-
IJCAI - Constraint Answer Set Programming versus satisfiability modulo theories
2016Co-Authors: Yuliya Lierler, Benjamin SusmanAbstract:Constraint Answer Set Programming is a promising research direction that integrates Answer Set Programming with constraint processing. It is often informally related to the field of Satisfiability Modulo Theories. Yet, the exact formal link is obscured as the terminology and concepts used in these two research areas differ. In this paper, we make the link between these two areas precise.
-
on relation between constraint Answer Set Programming and satisfiability modulo theories
Unpublished draft, 2016Co-Authors: Yuliya Lierler, Benjamin SusmanAbstract:Constraint Answer Set Programming is a promising research direction that integrates Answer Set Programming with constraint processing. It is often informally related to the field of Satisfiability Modulo Theories. Yet, the exact formal link is obscured as the terminology and concepts used in these two research areas differ. In this paper, by connecting these two areas, we begin the cross-fertilization of not only of the theoretical foundations of both areas but also of the existing solving technologies.
-
LPNMR - Performance Tuning in Answer Set Programming
Logic Programming and Nonmonotonic Reasoning, 2015Co-Authors: Matthew Buddenhagen, Yuliya LierlerAbstract:Performance analysis and tuning are well established software engineering processes in the realm of imperative Programming. This work is a step towards establishing the standards of performance analysis in the realm of Answer Set Programming – a prominent constraint Programming paradigm. We present and study the roles of human tuning and automatic configuration tools in this process. The case study takes place in the realm of a real-world Answer Set Programming application that required several hundred lines of code. Experimental results suggest that human-tuning of the logic Programming encoding and automatic tuning of the Answer Set solver are orthogonal (complementary) issues.
Joohyung Lee - One of the best experts on this subject based on the ideXlab platform.
-
functional stable model semantics and Answer Set Programming modulo theories
International Joint Conference on Artificial Intelligence, 2013Co-Authors: Michael Bartholomew, Joohyung LeeAbstract:Recently there has been an increasing interest in incorporating "intensional" functions in Answer Set Programming. Intensional functions are those whose values can be described by other functions and predicates, rather than being pre-defined as in the standard Answer Set Programming. We demonstrate that the functional stable model semantics plays an important role in the framework of "Answer Set Programming Modulo Theories (ASPMT)" --a tight integration of Answer Set Programming and satisfiability modulo theories, under which existing integration approaches can be viewed as special cases where the role of functions is limited. We show that "tight" ASPMT programs can be translated into SMT instances, which is similar to the known relationship between ASP and SAT.
-
IJCAI - Functional stable model semantics and Answer Set Programming modulo theories
2013Co-Authors: Michael Bartholomew, Joohyung LeeAbstract:Recently there has been an increasing interest in incorporating "intensional" functions in Answer Set Programming. Intensional functions are those whose values can be described by other functions and predicates, rather than being pre-defined as in the standard Answer Set Programming. We demonstrate that the functional stable model semantics plays an important role in the framework of "Answer Set Programming Modulo Theories (ASPMT)" --a tight integration of Answer Set Programming and satisfiability modulo theories, under which existing integration approaches can be viewed as special cases where the role of functions is limited. We show that "tight" ASPMT programs can be translated into SMT instances, which is similar to the known relationship between ASP and SAT.
-
circumscriptive event calculus as Answer Set Programming
International Joint Conference on Artificial Intelligence, 2009Co-Authors: Taewon Kim, Joohyung Lee, Ravi PallaAbstract:Recently, Ferraris, Lee and Lifschitz presented a general definition of a stable model that is similar to the definition of circumscription, and can even be characterized in terms of circumscription. In this paper, we show the opposite direction, which is, how to turn circumscription into the general stable model semantics, and based on this, how to turn circumscriptive event calculus into Answer Set programs. The reformulation of the event calculus in Answer Set Programming allows Answer Set solvers to be applied to event calculus reasoning, handling more expressive reasoning tasks than the current SAT-based approach. Our experiments also show clear computational advantages of the Answer Set Programming approach.
-
IJCAI - Circumscriptive event calculus as Answer Set Programming
2009Co-Authors: Taewon Kim, Joohyung Lee, Ravi PallaAbstract:Recently, Ferraris, Lee and Lifschitz presented a general definition of a stable model that is similar to the definition of circumscription, and can even be characterized in terms of circumscription. In this paper, we show the opposite direction, which is, how to turn circumscription into the general stable model semantics, and based on this, how to turn circumscriptive event calculus into Answer Set programs. The reformulation of the event calculus in Answer Set Programming allows Answer Set solvers to be applied to event calculus reasoning, handling more expressive reasoning tasks than the current SAT-based approach. Our experiments also show clear computational advantages of the Answer Set Programming approach.
