In a fluent, clear, and lively style this translation by two of Maslov's junior colleagues brings the work of the late Soviet scientist S. Yu. Maslov to a wider audience. Maslov was considered by his peers to be a man of genius who was making fundamental contributions in the fields of automatic theorem proving and computational logic. He published little, and those few papers were regarded as notoriously difficult. This book, however, was written for a broad audience of readers and (...) describes elegant examples of applications in such fields as computer science, artificial intelligence, operations research, economic modeling, and biological modeling, among others. The book also brings to light the work by the American mathematician E. L. Post, which inspired Maslov's own work in the development of a general theory and which has been long neglected by mathematicial logicians and systems theorists in the United States. The book's first chapter introduces the Rules of the Game. Part I, Mathematics of Calculi, covers E. L. Post's canonical systems, deductive systems and algorithms, and probabilistic calculi and deductive information. Part II, Horizonal Modeling, takes up a "toy" economy, the calculi of technological possibilities, and the development of rules. Part III, Vertical Modeling, deals with the topics of "to fight and to search" and the consequences of the asymmetry of cognitive mechanisms. Vladimir Lifschitz is affiliated with the Department of Computer Science at Stanford University, and Michael Gelfond with the Department of Electrical Engineering and Computer Science at the University of Texas, El Paso. Theory of Deductive Systems and Its Applicationsis included in the Foundation of Computing Series, edited by Michael Garey. (shrink)

cuted actions. It has been applied to several challenge problems in the theory of commonsense knowledge. We study the relationship between this formalism and other work on nonmonotonic reasoning and knowl-.

The work described in this report is motivated by the desire to test the expressive possibilities of action language C+. The Causal Calculator (CCalc) is a system that answers queries about action domains described in a fragment of that language. The Zoo World and the Traffic World have been proposed by Erik Sandewall in his Logic Modelling Workshop—an environment for communicating axiomatizations of action domains of nontrivial size. -/- The Zoo World consists of several cages and the exterior, gates between (...) them, and animals of several species, including humans. Actions in this domain include moving within and between cages, opening and closing gates, and mounting and riding animals. The Traffic World includes vehicles moving continuously between road crossings subject to a number of restrictions, such as speed limits and keeping a fixed safety distance away from other vehicles on the road. We show how to represent the two domains in the input language of CCalc, and how to use CCalc to test these representations. (shrink)

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.

“Toy worlds” involving actions, such as the blocks world and the Missionaries and Cannibals puzzle, are often used by researchers in the areas of commonsense reasoning and planning to illustrate and test their ideas. We would like to create a database of generalpurpose knowledge about actions that encodes common features of many action domains of this kind, in the same way as abstract algebra and topology represent common features of specific number systems. This paper is a report on the first (...) stage of this project—the design of an action description language in which this database will be written. The new language is an extension of the action language C+. Its main distinctive feature is the possibility of referring to other action descriptions in the definition of a new action domain. (shrink)

This is an expository article about the solution to the frame problem proposed in 1980 by Raymond Reiter. For years, his “frame default” remained untested and suspect. But developments in some seemingly unrelated areas of computer science—logic programming and satisfiability solvers—eventually exonerated the frame default and turned it into a basis for important applications.

Knowledge representation, which lies at the core of artificial intelligence, is concerned with encoding knowledge on computers to enable systems to reason automatically. The aims are to help readers make their computer smarter, handle qualitative and uncertain information, and improve computational tractability.

This is a review of some of the definitions of the concept of a stable model that have been proposed in the literature. These definitions are equivalent to each other, at least when applied to traditional Prologstyle programs, but there are reasons why each of them is valuable and interesting. A new characterization of stable models can suggest an alternative picture of the intuitive meaning of logic programs; or it can lead to new algorithms for generating stable models; or it (...) can work better than others when we turn to generalizations of the traditional syntax that are important from the perspective of answer set programming; or it can be more convenient for use in proofs; or it can be interesting simply because it demonstrates a relationship between seemingly unrelated ideas. (shrink)

in Handbook of Knowledge representation, Elsevier, 2008.

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)

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)

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.

This note shows how to formalize a small set of general facts about buying and selling. We begin with summarizing properties of buying/selling informally in English, and give examples of consequences of these assumptions. Then we formalize our assumptions in action language C+ with additive fluents and actions and test the adequacy of the proposed formalization using the Causal Calculator.

Safe first-order formulas generalize the concept of a safe rule, which plays an important role in the design of answer set solvers. We show that any safe sentence is equivalent, in a certain sense, to the result of its grounding—to the variable-free sentence obtained from it by replacing all quantifiers with multiple conjunctions and disjunctions. It follows that a safe sentence and the result of its grounding have the same stable models, and that stable models of a safe sentence can (...) be characterized by a formula of a simple syntactic form. (shrink)

This paper is motivated by the idea of interaction between two directions of research in knowledge representation: the design of action description languages and the development of libraries of reusable, general-purpose knowledge components. Writing an action description that characterizes actions in terms of their effects, as common today, can be compared to writing a program that does not use standard subroutines. We conjecture that a library of standard descriptions for a number of “basic” actions can facilitate writing, understanding and modifying (...) action descriptions. In this paper, we take some steps towards determining how such a library, written in the action language C+, can be used. When using an instance of a library action description, we relate the library constants to the domain-specific constants by providing definitions. Therefore, a theory of explicit definitions in C+ is developed. To illustrate the use of the library, we show how the action PushBox in the Monkey and Bananas domain can be described as a special case of the “library action” Move. (shrink)

The language of nonmonotonic causal theories, defined by Norman McCain and Hudson Turner, is an important formalism for representing properties of actions. For causal theories of a special kind, called definite, a simple translation into the language of logic programs under the answer set semantics is available. In this paper we define a similar translation for causal theories of a more general form, called al-.

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)

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

be irrelevant for achieving the given goal. We make this idea precise by defining, for an action description in language C+, when a subset of its..

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

This note is about the “calculational style” of presenting proofs introduced by Dijkstra and Scholten and adopted in some books on theoretical computer science. We define the concept of a calculation, which is a formal counterpart of the idea of a calculational proof. The definition is in terms of a new formalization DS of predicate logic. Any proof tree in the system DS can be represented as a sequence of calculations. This fact shows that any logically valid predicate formula has (...) a calculational proof. (shrink)

(Click here for selected papers published before 1996, and here for papers published after 2000.) V. Lifschitz, Foundations of logic programming ," in Principles of Knowledge Representation , CSLI Publications, 1996, pp. 69-127. E. Giunchiglia, N. Kartha and V. Lifschitz, Representing action: indeterminacy and ramifications ," Artificial Intelligence , Vol. 95, 1997, pp. 409-443. V. Lifschitz, On the logic of causal explanation ," Artificial Intelligence , Vol. 96, 1997, pp. 451-465. V. Lifschitz, Two components of an action language ," Annals (...) of Mathematics and Artificial Intelligence , Vol. 21, 1997, pp. 305-320. V. Lifschitz, Situation calculus and causal logic ," in Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning, 1998, pp. 536-646. (shrink)

Safe first-order formulas generalize the concept of a safe rule, which plays an important role in the design of answer set solvers. We show that any safe sentence is equivalent, in a certain sense, to the result of its grounding—to the variable-free sentence obtained from it by replacing all quantifiers with multiple conjunctions and disjunctions. It follows that a safe sentence and the result of its grounding have the same stable models, and that stable models of a safe sentence can (...) be characterized by a formula of a simple syntactic form. (shrink)

(Click here for the papers published between 1996 and 2000, and here for more recent papers.) V. Lifschitz, On the semantics of STRIPS ," in: Reasoning about Actions and Plans , 1987, pp. 1-9. M. Gelfond and V. Lifschitz, The stable model semantics for logic programming ," in Logic Programming: Proceedings of the Fifth International Conference and Symposium , 1988, pp. 1070-1080.

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)

structures, or interpretations, in the sense of first-order logic. In C+, on the other hand, a state is an interpreta-.

Action description language C+ is more expressive than ADL in many ways; for instance, it addresses the ramification problem. On the other hand, ADL is based on first-order logic, while C+ is only propositional; expressions with variables, which are frequently used when action domains are described in C+, are merely..

“Toy worlds” involving actions, such as the Blocks World and the Monkey and Bananas domain, are often used by researchers in the areas of commonsense reasoning and planning to illustrate and test their ideas. Many of the axioms found in descriptions of these toy worlds are expressions of generalpurpose knowledge, though they are often cast in a form only useful for solving one specific problem and are not faithful representations of general facts that can be used in other domains. Instead (...) of using such domain-specific axioms for each problem, we are building a general-purpose library of action descriptions which can be referred to in descriptions of many action domains. The library is being written in the modular action description language MAD, an extension of the action language ·. In this paper we present an initial version of some of our library modules, along with a new formalization of the Monkey and Bananas domain that uses the library. Most of the axioms in this formalization come from the library, with only a few domain-specific axioms needed. (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.