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 via ASP. 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. (shrink)

This paper discusses an extension of Answer Set Programming called Hybrid Answer Set Programming which allows the user to reason about dynamical systems that exhibit both discrete and continuous aspects. The unique feature of Hybrid ASP is that it allows the use of ASP type rules as controls for when to apply algorithms to advance the system to the next position. That is, if the prerequisites of a rule are satisfied and the constraints of the rule (...) are not violated, then the algorithm associated with the rule is invoked. (shrink)

dynamic ontologies must be inferred and populated in part from the reference corpora themselves, but ontological rela-.

Answer set programming (ASP) is a form of declarative programming oriented towards difficult search problems. As an outgrowth of research on the use of nonmonotonic reasoning in knowledge representation, it is particularly useful in knowledge-intensive applications. ASP programs consist of rules that look like Prolog rules, but the computational mechanisms used in ASP are different: they are based on the ideas that have led to the creation of fast satisfiability solvers for propositional logic.

There has been considerable discussion in the past about the assumptions and basis of different ethical rules. For instance, it is commonplace to say that ethical rules are defaults rules, which means that they tolerate exceptions. Some authors argue that morality can only be grounded in particular cases while others defend the existence of general principles related to ethical rules. Our purpose here is not to justify either position, but to try to model general ethical rules with artificial intelligence formalisms (...) and to compute logical consequences of different ethical theories. More precisely, this is an attempt to show that progress in non-monotonic logics, which simulates default reasoning, could provide a way to formalize different ethical conceptions. From a technical point of view, the model developed in this paper makes use of the Answer Set Programming (ASP) formalism. It is applied comparatively to different ethical systems with respect to their attitude towards lying. The advantages of such formalization are two-fold: firstly, to clarify ideas and assumptions, and, secondly, to use solvers to derive consequences of different ethical conceptions automatically, which can help in a rigorous comparison of ethical theories. (shrink)

Felicitous models were defined by Kit Fine in 1987 for the purpose of describing the semantics of negation in the programming language Prolog. They are often referred to as stable models, or answer sets. Years later, sophisticated software systems for generating answer sets were designed, and they became the basis of a new programming paradigm, called answer set programming. That programming method is used now for solving computational problems in many areas of science (...) and technology. This chapter traces the early history of felicitous models and the ways in which that idea contributed to computer science. (shrink)

affects the collection of answer sets. In particular, it is useful to be able to describe the effects of adding definitions to a program with nested expressions, in view of the relation of this class of programs to the input language of the answer set programming system sMonELs. In this..

As is well known, answer-set programs do not satisfy the replacement property in general, i.e., programs and that are equivalent may cease to be so when they are put in the context of some other program, i.e., and may have different answer sets. Lifschitz, Pearce, and Valverde thus introduced strong equivalence for context-independent equivalence, and proved that such equivalence holds between given programs and iff and are equivalent theories in the monotonic logic of here-and-there. In this article, we (...) consider a related question: given a program, does there exist some program from a certain class of programs such that and are equivalent under a given notion of equivalence? Furthermore, if the answer to this question is positive, how can we recast as an equivalent program from? In particular, we consider classes of programs that emerge by allowing disjunction and/or negation, and as equivalence notions we consider strong, uniform, and ordinary equivalence. Based on general model-theoretic properties and a novel form of canonical programs, we develop semantic characterisations for the existence of such a program, determine the computational complexity of checking existence, and provide rewriting rules for recasting. (shrink)

In the context of the emerging Semantic Web and the quest for a common logical framework underpinning its architecture, the relation of rule-based languages such as Answer Set Programming (ASP) and ontology languages such as the Web Ontology Language (OWL) has attracted a lot of attention in the literature over the past years. With its roots in Deductive Databases and Datalog though, ASP shares much more commonality with another Semantic Web standard, namely the Simple Protocol and RDF Query (...) Language (SPARQL). In this paper, we take the recent approval of the SPARQL1.1 standard by the World Wide Web consortium (W3C) as an opportunity to introduce this standard to the Logic Programming community by providing a translation of SPARQL1.1 into ASP. In this translation, we explain and highlight peculiarities of the new W3C standard. Along the way, we survey existing literature on foundations of SPARQL and SPARQL1.1, and also combinations of SPARQL with ontology and rules languages. Thereby, apart from providing the means to implement and support SPARQL natively within Logic Programming engines and particularly ASP engines, we hope to pave the way for further research on a common logical framework for Semantic Web languages, including query languages, from an ASP point of view. (shrink)

applied, for instance, to developing a decision support system for the Space Shuttle INogueira et al., 2001] and to graph-theoretic problems arising in..

Answer Set Programming is a new paradigm based on logic programming. The main component of answer set programming is a system that finds the answer sets of logic programs. During the computation of an answer set, systems are faced with choice points where they have to select a literal and assign it a truth value. Generally, systems utilize some heuristics to choose new literals at the choice points. The heuristic used is one of (...) the key factors for the performance of the system. A new heuristic for answer set programming has been developed. This heuristic is inspired by hierarchical planning. The notion of criticality, which was introduced for generating abstraction hierarchies in hierarchical planning, is used in this heuristic. The resulting system (CSMODELS) uses this new heuristic in a static way. CSMODELS is based on the system SMODELS. The experimental results show that this new heuristic is promising for answer set programming. A comparison of search times with SMODELS demonstrate CSMODELS’ usefulness. (shrink)

In a recent paper, Ferraris, Lee and Lifschitz conjectured that the concept of a stable model of a first-order formula can be used to treat some answer set programming expressions as abbreviations. We follow up on that suggestion and introduce an answer set programming language that defines the mean- ing of counting and choice by reducing these constructs to first-order formulas. For the new language, the concept of a safe program is defined, and its semantic role (...) is investigated. We compare the new language with the concept of a disjunc- tive program with aggregates introduced by Faber, Leone and Pfeifer, and discuss the possibility of implementing a frag- ment of the language by translating it into the input language of the answer set solver DLV. The language is also compared with cardinality constraint programs defined by Syrjänen. (shrink)

In Minker and Rajasekar (J Log Program 9(1):45–74, 1990), Minker proposed a semantics for negation-free disjunctive logic programs that offers a natural generalisation of the fixed point semantics for definite logic programs. We show that this semantics can be further generalised for disjunctive logic programs with classical negation, in a constructive modal-theoretic framework where rules are built from _claims_ and _hypotheses_, namely, formulas of the form \(\Box \varphi \) and \(\Diamond \Box \varphi \) where \(\varphi \) is a literal, respectively, (...) yielding a “base semantics” for general disjunctive logic programs. Model-theoretically, this base semantics is expressed in terms of a classical notion of logical consequence. It has a complete proof procedure based on a general form of the cut rule. Usually, alternative semantics of logic programs amount to a particular interpretation of nonclassical negation as “failure to derive.” The counterpart in our framework is to complement the original program with a set of hypotheses required to satisfy specific conditions, and apply the base semantics to the resulting set. We demonstrate the approach for the answer set semantics. The proposed framework is purely classical in mainly three ways. First, it uses classical negation as unique form of negation. Second, it advocates the computation of logical consequences rather than of particular models. Third, it makes no reference to a notion of preferred or minimal interpretation. (shrink)

Logic programs under answer set semantics have become popular as a knowledge representation formalism in Artificial Intelligence. In this paper we investigate the possibility of using answer sets for qualitative decision making. Our approach is based on an extension of the formalism, called logic programs with ordered disjunction (LPODs). These programs contain a new connective called ordered disjunction. The new connective allows us to represent alternative, ranked options for problem solutions in the heads of rules: A × B (...) intuitively means: if possible A, but if A is not possible then at least B. The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets. We show that LPODs can serve as a basis for qualitative decision making. (shrink)

One of the major reasons for the success of answer set programming in recent years was the shift from a theorem proving to a constraint programming view: problems are represented such that stable models, respectively answer sets, rather than theorems correspond to solutions. This shift in perspective proved extremely fruitful in many areas. We believe that going one step further from a “hard” to a “soft” constraint programming paradigm, or, in other words, to a paradigm (...) of qualitative optimization, will prove equally fruitful. In this paper we try to support this claim by showing that several generic problems in logic based problem solving can be understood as qualitative optimization problems, and that these problems have simple and elegant formulations given adequate optimization constructs in the knowledge representation language. (shrink)

It was proved by Odintsov and Pearce that the logic is a deductive base for paraconsistent answer set semantics of logic programs with two kinds of negation. Here we describe the lattice of logics extending, characterise these logics via classes of -models, and prove that none of the proper extensions of is a deductive base for PAS.

This book constitutes the refereed proceedings of the 20th International Conference on Logic Programming, ICLP 2004, held in Saint-Malo, France in September 2004. The 28 revised full papers and 16 poster papers presented together with 2 invited papers were carefully reviewed and selected from 70 submissions. The papers are organized in topical sections on program analysis, constraints, alternative programming paradigms, answer set programming, and implementation.

In this paper, I set out some basic elements of a deontic logic with an implementation appropriate for handling conflicting legal obligations for purposes of programming autonomous machine agents. Kantian justice demands that the prescriptive system of enforceable public laws be consistent, yet statutes or case holdings may often describe legal obligations that contradict; moreover, even fundamental constitutional rights may come into conflict. I argue that a deontic logic of the law should not try to work around such conflicts (...) but, instead, identify and expose them so that the rights and duties that generate inconsistencies in public law can be explicitly qualified and the conflicts resolved. I then argue that a credulous, non-monotonic deontic logic can describe inconsistent legal obligations while meeting Kant’s demand for consistency in the prescriptive system of public law. Finally, I propose an implementation of this logic via a modified form of “answer set programming,” which I demonstrate with some simple examples. (shrink)

This book constitutes the refereed proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2004, held in Fort Lauderdale, Florida, USA in January 2004. The 24 revised full papers presented together with 8 system descriptions were carefully reviewed and selected for presentation. Among the topics addressed are declarative logic programming, nonmonotonic reasoning, knowledge representation, combinatorial search, answer set programming, constraint programming, deduction in ontologies, and planning.

Recently we proposed a method of compiling prioritized circumscription into answer set programming. However, its encoding has the guess and check structure, where the candidates are generated by the guess program and the check is expressed by the inconsistency of the check program. In this paper, we present another method which compiles prioritized circumscription into a single general disjunctive program by means of integration of the guess and check programs. The answer sets of the transformed GDP yield (...) models of a given circumscription by emulating the inconsistency of the check program using integrity constraints. Thanks to our integration technique, the circumscriptive theorem prover to evaluate a query with respect to prioritized circumscription is easily established by expressing the inconsistency check in a single GDP. Our experimental results show that the performance of the tool we have implemented using our new method has not only improved remarkably, i.e. reduction of runtime as compared to our previous method, but has also exceeded that of the recently developed software tool, prio_circ2dlp, for prioritized circumscription as far as our experiments are concerned. (shrink)

The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about (...) contacts between prehistoric linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages. (shrink)

The motivation of this study is that Reiter’s default theory as well as assumption-based argumentation frameworks corresponding to default theories have difficulties in handling disjunctive information, while a disjunctive default theory (ddt) avoids them. This paper presents the semantic correspondence between generalized assumption-based argumentation (ABA) and extended disjunctive logic programming as well as the correspondence between ABA and nonmonotonic reasoning approaches such as disjunctive default logic and prioritized circumscription. To overcome the above-mentioned difficulties of ABA frameworks corresponding to default (...) theories, we propose an assumption-based framework (ABF) translated from an extended disjunctive logic program (EDLP) since an EDLP can be translated into a ddt. Our ABF incorporates explicit negation and the connective of disjunction “|” to Heyninck and Arieli’s ABF induced by a disjunctive logic program. In this paper, first, we show how arguments are constructed from disjunctive rules in our proposed ABF. Then, we show the correspondence between answer sets of an EDLP P and stable extensions of the ABF translated from P with trivialization rules. After defining rationality postulates, we show answer sets of a consistent EDLP are captured by consistent stable extensions of the translated ABF with no trivialization rules. Finally, we show the correspondence between ABA and disjunctive default logic (resp. prioritized circumscription). The relation between ABA and possible model semantics of EDLPs is also discussed. (shrink)

In this paper, we study the introduction of modal past temporal operators in Temporal Equilibrium Logic, an hybrid formalism that mixes linear-time modalities and logic programs interpreted under stable models and their characterisation in terms of Equilibrium Logic. We show that Kamp’s translation can also be used to translate the new extension of TEL with past operators into Quantified Equilibrium Logic. Additionally, we provide a method for removing past operators that consists in replacing past-time subformulas by fresh auxiliary atoms, obtaining (...) an equivalent formula, modulo the original alphabet. (shrink)