Classical fixpoint semantics for logic programs is based on the TP immediate consequence operator. The Kripke/Kleene, three-valued, semantics uses ΦP, which extends TP to Kleene’s strong three-valued logic. Both these approaches generalize to cover logic programming systems based on a wide class of logics, provided only that the underlying structure be that of a bilattice. This was presented in earlier papers. Recently well-founded semantics has become influential for classical logic programs. We show how the well-founded approach also extends naturally to (...) the same family of bilatticebased programming languages that the earlier fixpoint approaches extended to. Doing so provides a natural semantics for logic programming systems that have already been proposed, as well as for a large number that are of only theoretical interest. And finally, doing so simplifies the proofs of basic results about the well-founded semantics, by stripping away inessential details. (shrink)

Argumentation Frameworks provide a fruitful basis for exploring issues of defeasible reasoning. Their power largely derives from the abstract nature of the arguments within the framework, where arguments are atomic nodes in an undifferentiated relation of attack. This abstraction conceals different senses of argument, namely a single-step reason to a claim, a series of reasoning steps to a single claim, and reasoning steps for and against a claim. Concrete instantiations encounter difficulties and complexities as a result of conflating these senses. (...) To distinguish them, we provide an approach to instantiating AFs in which the nodes are restricted to literals and rules, encoding the underlying theory directly. Arguments in these senses emerge from this framework as distinctive structures of nodes and paths. As a consequence of the approach, we reduce the effort of computing argumentation extensions, which is in contrast to other approaches. Our framework retains the theoretical and computational bene.. (shrink)

In this paper, we prove the correspondence between complete extensions in abstract argumentation and 3-valued stable models in logic programming. This result is in line with earlier work of [6] that identified the correspondence between the grounded extension in abstract argumentation and the well-founded model in logic programming, as well as between the stable extensions in abstract argumentation and the stable models in logic programming.

ABSTRACTThis paper studies abduction in abstract argumentation frameworks. Given an argument, an agent verifies whether the argument is justified or not in its argumentation framework. If the argument is not justified in the argumentation framework, the agent seeks conditions to explain the justification state by hypothesising arguments in the universal argumentation framework. We formulate such abductive reasoning in argumentation semantics and provide its computation in logic programming. We also apply abduction to enforcement and simple dialogue games in argumentation frameworks.

The infinite-valued semantics was introduced in Rondogiannis and Wadge (2005) as a purely logical way for capturing the meaning of well-founded negation in logic programming. The purpose of this paper is threefold: first, to give a non-technical introduction to the infinite-valued semantics; second, to discuss the applicability of the infinite-valued approach to syntactically richer extensions of logic programming; and third, to present the main open problems whose resolution would further enhance the applicability of the technique.

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)

The paper provides a preliminary study of algebraic semantics for modal and superintuitionistic non-monotonic logics. The main question answered is: how can non-monotonic inference be understood algebraically?

We propose an extension of answer sets, that we call safe beliefs, that can be used to study several properties and notions of answer sets and logic programming from a more general point of view. Our definition, based on intuitionistic logic and following ideas from D. Pearce [Stable inference as intuitionistic validity, Logic Programming 38 79–91], also provides a general approach to define several semantics based on different logics or inference systems. We prove that, in particular, intuitionistic logic can be (...) replaced with any other proper intermediate logic without modifying the resulting semantics. We also show that the answer set semantics satisfies an important property, the “extension by definition”, that can be used to construct program translations. As a result we are able to provide a polynomial translation from propositional theories into the class of disjunctive programs. (shrink)

In this paper, we propose an annotated logic program called aVALPSN to dealwith defeasible reasoning. We propose a translation from Billington’s defeasible theory into VALPSN and clarify the relation between them based onthe translation.

Fixpoint semantics are provided for ambiguity blocking and propagating variants of Nute's defeasible logic. The semantics are based upon the well-founded semantics for logic programs. It is shown that the logics are sound with respect to their counterpart semantics and complete for locally finite theories. Unlike some other nonmonotonic reasoning formalisms such as Reiter's default logic, the two defeasible logics are directly skeptical and so reject floating conclusions. For defeasible theories with transitive priorities on defeasible rules, the logics are shown (...) to satisfy versions of Cut and Cautious Monotony. For theories with either conflict sets closed under strict rules or strict rules closed under transposition, a form of Consistency Preservation is shown to hold. The differences between the two logics and other variants of defeasible logic—specifically those presented by Billington, Antoniou, Governatori, and Maher—are discussed. (shrink)

Nonmonotonic causal logic is a knowledge representation language designed for describing domains that involve actions and change. The process of literal completion, similar to program completion familiar from the theory of logic programming, can be used to translate some nonmonotonic causal theories into classical logic. Its applicability is restricted, however, to theories that deal with truth-valued fluents, represented by predicate symbols. In this note we introduce functional completion—a more general process that can be applied to causal theories in which fluents (...) are treated as functions. (shrink)

In this article, we compare the expressive powers of classes of normal logic programs that are obtained by constraining the number of positive subgoals in the bodies of rules. The comparison is based on the existence/nonexistence of polynomial, faithful, and modular translation functions between the classes. As a result, we obtain a strict ordering among the classes under consideration. Binary programs are shown to be as expressive as unconstrained programs but strictly more expressive than unary programs which, in turn, are (...) strictly more expressive than atomic programs. We also take propositional theories into consideration and prove them to be strictly less expressive than atomic programs. In spite of the gap in expressiveness, we develop a faithful but non-modular translation function from normal programs to propositional theories. We consider this as a breakthrough due to sub-quadratic time complexity |). Furthermore, we present a prototype implementation of the translation function and demonstrate its promising performance with SAT solvers using three benchmark problems. (shrink)

In this paper we present the syntax and semantics of a temporal action language named Alan, which was designed to model interactive multimedia presentations where the Markov property does not always hold. In general, Alan allows the specification of systems where the future state of the world depends not only on the current state, but also on the past states of the world. To the best of our knowledge, Alan is the first action language which incorporates causality with temporal formulas. (...) In the process of defining the effect of actions we define the closure with respect to a path rather than to a state, and show that the non-Markovian model is an extension of the traditional Markovian model. Finally, we establish relationship between theories of Alan and logic programs. (shrink)

We present an infinite-game characterization of the well-founded semantics for function-free logic programs with negation. Our game is a simple generalization of the standard game for negation-less logic programs introduced by van Emden [M.H. van Emden, Quantitative deduction and its fixpoint theory, Journal of Logic Programming 3 37–53] in which two players, the Believer and the Doubter, compete by trying to prove a query. The standard game is equivalent to the minimum Herbrand model semantics of logic programming in the sense (...) that a query succeeds in the minimum model semantics iff the Believer has a winning strategy for the game which begins with the Doubter doubting this query. The game for programs with negation that we propose follows the same rules as the standard one, except that the players swap roles every time the play “passes through” negation. We start our investigation by establishing the determinacy of the new game by using some classical tools from the theory of infinite-games. Our determinacy result immediately provides a novel and purely game-theoretic characterization of the semantics of negation in logic programming. We proceed to establish the connections of the game semantics to the existing semantic approaches for logic programming with negation. For this purpose, we first define a refined version of the game that uses degrees of winning and losing for the two players. We then demonstrate that this refined game corresponds exactly to the infinite-valued minimum model semantics of negation [P. Rondogiannis,W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational Logic 6 441–467]. This immediately implies that the unrefined game is equivalent to the well-founded semantics. (shrink)

We introduce a subclass of Kripke's fixed points in which falsehood is the preferred truth value. In all of these the truthteller evaluates to false, while the liar evaluates to undefined (or overdefined). The mathematical structure of this family of fixed points is investigated and is shown to have many nice features. It is noted that a similar class of fixed points, preferring truth, can also be studied. The notion of intrinsic is shown to relativize to these two subclasses. The (...) mathematical ideas presented here originated in investigations of so-called stable models in the semantics of logic programming. (shrink)

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)

Recently, Brass and Dix showed 143–165) that the well founded semantics WFS can be defined as a confluent calculus of transformation rules. This led not only to a simple extension to disjunctive programs 167–213), but also to a new computation of the well-founded semantics which is linear for a broad class of programs. We take this approach as a starting point and generalize it considerably by developing a general theory of Confluent LP-systems CS . Such a system CS is a (...) rewriting system on the set of all logic programs over a fixed signature L and it induces in a natural way a canonical semantics. Moreover, we show four important applications of this theory: most of the well-known semantics are induced by confluent LP-systems , there are many more transformation rules that lead to confluent LP-systems , semantics induced by such systems can be used to model aggregation , the new systems can be used to construct interesting counterexamples to some conjectures about the space of well-behaved semantics. (shrink)

Formal approaches that aim at representing human reasoning should be evaluated based on how humans actually reason. One way of doing so is to investigate whether psychological findings of human reasoning patterns are represented in the theoretical model. The computational logic approach discussed here is the so-called weak completion semantics which is based on the three-valued ᴌukasiewicz logic. We explain how this approach adequately models Byrne’s suppression task, a psychological study where the experimental results show that participants’ conclusions systematically deviate (...) from the classical logically correct answers. As weak completion semantics is a novel technique in the field of computational logic, it is important to examine how it corresponds to other already established non-monotonic approaches. For this purpose we investigate the relation of weak completion with respect to completion and three-valued stable model semantics. In particular, we show that well-founded semantics, a widely accepted approach in the field of non-monotonic reasoning, corresponds to weak completion semantics for a specific class of modified programs. (shrink)

This special issue presents a selection of papers in Knowledge Representation in Artificial Intelligence , intended to illustrate the depth and breadth of current research in the area. It comes just over 25 years since a similar special issue of the Journal of Philosophical Logic appeared on the topic Philosophical Logic and Artificial Intelligence [15]. This latter special issue covered work addressing the use of logic, in one form or another, for representing and reasoning with knowledge. The papers of the (...) 1988 special issue give a good indication of major themes of research at the time: reasoning about belief and knowledge [5], tractable logical reasoning [10], nonmonotonicity [11], and reasoning about action [13]. These topics can be considered to be centrally in KR; the current issue then also serves to indicate how the field has broadened and evolved over the last 25 years.Traditionally the area of Knowledge Representation has been seen as “the field of study concerned w .. (shrink)

Formal models of argumentation have been investigated in several areas, from multi-agent systems and artificial intelligence (AI) to decision making, philosophy and law. In artificial intelligence, logic-based models have been the standard for the representation of argumentative reasoning. More recently, the standard logic-based models have been shown equivalent to standard connectionist models. This has created a new line of research where (i) neural networks can be used as a parallel computational model for argumentation and (ii) neural networks can be used (...) to combine argumentation, quantitative reasoning and statistical learning. At the same time, non-standard logic models of argumentation started to emerge. In this paper, we propose a connectionist cognitive model of argumentation that accounts for both standard and non-standard forms of argumentation. The model is shown to be an adequate framework for dealing with standard and non-standard argumentation, including joint-attacks, argument support, ordered attacks, disjunctive attacks, meta-level attacks, self-defeating attacks, argument accrual and uncertainty. We show that the neural cognitive approach offers an adequate way of modelling all of these different aspects of argumentation. We have applied the framework to the modelling of a public prosecution charging decision as part of a real legal decision making case study containing many of the above aspects of argumentation. The results show that the model can be a useful tool in the analysis of legal decision making, including the analysis of what-if questions and the analysis of alternative conclusions. The approach opens up two new perspectives in the short-term: the use of neural networks for computing prevailing arguments efficiently through the propagation in parallel of neuronal activations, and the use of the same networks to evolve the structure of the argumentation network through learning (e.g. to learn the strength of arguments from data). (shrink)

RASP is a recent extension to Answer Set Programming (ASP) that permits declarative specification and reasoning on the consumption and production of resources. ASP can be seen as a particular case of RASP. In this paper, we study the relationship between linear logic and RASP problem specification. We prove that RASP programs can be translated into (a fragment of) linear logic, and vice versa. In doing so, we introduce a linear logic representation of default negation as understood in ASP. We (...) are also able to establish a link between linear logic and here-and-there (HT) logic. (shrink)

This paper introduces and studies a declarative framework for updating views over indefinite databases. An indefinite database is a database with null values that are represented, following the standard database approach, by a single null constant. Typically a database is represented by a single set of facts |$D$| that model what is known to be true. This paper proposes a model of an indefinite extensional database that is more expressive with respect to the closed-world assumption (CWA) adapted for the setting (...) of indefinite databases (Libkin, 1995, A semantics-based approach to design of query languages for partial information. In Semantics in Databases, vol. 1358 of LNCS, pp. 170–208. Springer; der Meyden, 1998, Logical approaches to incomplete information: a survey. In Logics for Databases and Information Systems, pp. 307–356. Kluwer Academic Publishers, Norwell, MA, USA). More specifically, in our model, databases are determined by two sets of facts: |$D$| representing, as usual, all facts that are true in the database, and |$E$| that is meant to represent exceptions to the ‘unknown range’, i.e. facts that cannot be unknown. Intuitively, unless they are explicitly implied to be true by the first set, the facts specified as exceptions are assumed false. The semantics is given by means of a two-level CWA tailored to the case of indefinite information. The paper characterizes the semantics of indefinite databases in terms of their possible worlds that are obtained by instantiating occurrences of null values by concrete constants and defines several classes of database repairs that realize view-update requests. Most notable is the class of constrained repairs. Constrained repairs change the database ‘minimally’and avoid making arbitrary commitments. They narrow down the space of alternative ways to fulfill the view-update request to those that are grounded, in a certain strong sense, in the database, the view and the view-update request. (shrink)

In this paper, we present a discussion game for argumentation under stable semantics. Our work is inspired by Vreeswijk and Prakken, who have defined a similar game for preferred semantics. In the current paper, we restate Vreeswijk and Prakken's work using the approach of argument labellings and then show how it can be adjusted for stable semantics. The nature of the resulting argument game is somewhat unusual, since stable semantics does not satisfy the property of relevance.

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)

This article aims to achieve two goals: to show that probability is not the only way of dealing with uncertainty ; and to provide evidence that logic-based methods can well support reasoning with uncertainty. For the latter claim, two paradigmatic examples are presented: logic programming with Kleene semantics for modelling reasoning from information in a discourse, to an interpretation of the state of affairs of the intended model, and a neural-symbolic implementation of input/output logic for dealing with uncertainty in dynamic (...) normative contexts. (shrink)

Since the earliest formalisation of default logic by Reiter many contributions to this appealing approach to nonmonotonic reasoning have been given. The different formalisations are here presented in a general framework that gathers the basic notions, concepts and constructions underlying default logic. Our view is to interpret defaults as special rules that impose a restriction on the juxtaposition of monotonic Hubert-style proofs of a given logicL. We propose to describe default logic as a logic where the juxtaposition of default proofs (...) is subordinate to a restriction condition . Hence a default logic is a pair (L, ) where properties of the logic , like compactness, can be interpreted through the restriction condition . Different default systems are then given a common characterization through a specific condition on the logicL. We also prove cumulativity for any default logic (L, ) by slightly modifying the notion of default proof. We extend, in fact, the language ofL in a way close to that followed by Brewka in the formulation of his cumulative default system. Finally we show the existence of infinitely many intermediary default logics, depending on and called linear logics, which lie between Reiter's and ukaszewicz' versions of default logic. (shrink)

Over recent years, various semantics have been proposed for dealing with updates in the setting of logic programs. The availability of different semantics naturally raises the question of which are most adequate to model updates. A systematic approach to face this question is to identify general principles against which such semantics could be evaluated. In this paper we motivate and introduce a new such principle the refined extension principle. Such principle is complied with by the stable model semantics for (single) (...) logic programs. It turns out that none of the existing semantics for logic program updates, even though generalisations of the stable model semantics, comply with this principle. For this reason, we define a refinement of the dynamic stable model semantics for Dynamic Logic Programs that complies with the principle. (shrink)

Normative systems have been advocated as an effective tool to regulate interaction in multi-agent systems. The use of deontic operators and the ability to represent defeasible information are known to be two fundamental ingredients to represent and reason about normative systems. In this paper, after introducing a framework that combines standard deontic logic and non-monotonic logic programming, deontic logic programs (DLP), we tackle the fundamental problem of equivalence between normative systems using a deontic extension of David Pearce’s Equilibrium Logic and (...) its monotonic basis, the logic of Here-and-There. We also show how deontic logic programs can be used to represent and reason about normative systems, and establish a strong connection with input-output logic. (shrink)

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 characterisation for the stable models semantics of logic programs) with Linear-Time Temporal Logic.

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)

We present a logic programming language, which we call Proflog, with an operational semantics based on tableaus, and a denotational semantics based on supervaluations. We show the two agree. Negation is well-behaved, and semantic non-computability issues do not arise. This is accomplished essentially by dropping a domain closure requirement. The cost is that intuitions developed through the use of classical logic may need modification, though the system is still classical at a level once removed. Implementation problems are discussed very briefly (...) — the thrust of the paper is primarily theoretical. (shrink)