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 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)

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)

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.

One approach to the paradoxes of self-referential languages is to allow some sentences to lack a truth value (or to have more than one). Then assigning truth values where possible becomes a fixpoint construction and, following Kripke, this is usually carried out over a partially ordered family of three-valued truth-value assignments. Some years ago Matt Ginsberg introduced the notion of bilattice, with applications to artificial intelligence in mind. Bilattices generalize the structure Kripke used in a very natural way, while making (...) the mathematical machinery simpler and more perspicuous. In addition, work such as that of Yablo fits naturally into the bilattice setting. What I do here is present the general background of bilattices, discuss why they are natural, and show how fixpoint approaches to truth in languages that allow self-reference can be applied. This is not new work, but rather is a summary of research I have done over many years. (shrink)

The variety of semantical approaches that have been invented for logic programs is quite broad, drawing on classical and many-valued logic, lattice theory, game theory, and topology. One source of this richness is the inherent non-monotonicity of its negation, something that does not have close parallels with the machinery of other programming paradigms. Nonetheless, much of the work on logic programming semantics seems to exist side by side with similar work done for imperative and functional programming, with relatively minimal contact (...) between communities. In this paper we summarize one variety of approaches to the semantics of logic programs: that based on fixpoint theory. We do not attempt to cover much beyond this single area, which is already remarkably fruitful. We hope readers will see parallels with, and the divergences from the better known fixpoint treatments developed for other programming methodologies. (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)

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)

The article develops and justifies, on the basis of the epistemological argumentation theory, two central pieces of the theory of evaluative argumentation interpretation: 1. criteria for recognizing argument types and 2. rules for adding reasons to create ideal arguments. Ad 1: The criteria for identifying argument types are a selection of essential elements from the definitions of the respective argument types. Ad 2: After presenting the general principles for adding reasons (benevolence, authenticity, immanence, optimization), heuristics are proposed for finding missing (...) reasons, for deductive arguments, e.g., semantic tableaux are suggested. (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)

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)

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)

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 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.

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.

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)

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)

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 existence of a model for a logic program is generally established by lattice-theoretic arguments. We present three examples to show that metric methods can often be used instead, generally in a direct, straightforward way. One example is a game program, which is not stratified or locally stratified, but which has a unique supported model whose existence is easily established using metric methods. The second example is a program without a unique supported model, but having a part that is (...) ‘well-behaved.’ The third example is a program in which one part depends on another, illustrating how modularity might be treated metrically. Finally we use ideas from this third example to prove a general result from [3]. The intention in presenting these examples and the theorem is to stimulate interest in.. (shrink)

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)

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.

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)

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)

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)

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 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)

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)

The family of all stable models for a logic program has a surprisingly simple overall structure, once two naturally occurring orderings are made explicit. In a so-called knowledge ordering based on degree of definedness, every logic program P has a smallest stable model, sk P — it is the well-founded model. There is also a dual largest stable model, S k P, which has not been considered before. There is another ordering based on degree of truth. Taking the meet and (...) the join, in the truth ordering, of the two extreme stable models sk P and S.. (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)

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)

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)