Modal nonmonotonic logics demodalized

The study of the relation between default logic and modal nonmonotonic logics has been mostly concerned with the task of translating default logic to autoepistemic or some other modal nonmonotonic logic. Here, we discuss the reverse problem, that is, the possibility of translating modal nonmonotonic logics into default-type systems formulated in the language without modal operators. To this end, we first consider a reformulation of both formalisms in terms of what we call default consequence relations. These consequence relations turn out to be especially suitable for studying default and modal nonmonotonic reasoning. We show, in particular, that different kinds of such reasoning naturally correspond to different structural rules imposed on default consequence relations. Our main results also demonstrate that all modal nonmonotonic objects considered have exact nonmodal counterparts. As an immediate consequence of these results, we obtain a method of reducing common types of modal nonmonotonic reasoning to nonmodal default reasoning.     

Multi-modal nonmonotonic logics of minimal knowledge

In this paper we introduce multi-modal logics of minimal knowledge. Such a family of logics constitutes the first proposal in the field of epistemic nonmonotonic logic in which the three following aspects are simultaneously addressed: (1) the possibility of formalizing multiple agents through multiple modal operators; (2) the possibility of using first-order quantification in the modal language; (3) the possibility of formalizing nonmonotonic reasoning abilities for the agents modeled, based on the principle of minimal knowledge. We illustrate the expressive capabilities of multi-modal logics of minimal knowledge to provide a formal semantics to peer-to-peer data integration systems, which constitute one of the most recent and complex architectures for distributed information systems.      

Temporal logics in AI: Semantical and ontological considerations

One way to represent temporal information in a logical formalism is by associating “proposition types” with time points or time intervals. The way this is usually done in AI is by “reifying” propositions, so that what otherwise would have been formulas actually appear as arguments to some “predicate,” say TRUE, as in TRUE(t₁, t₂, COLOR(HOUSE, RED)). This way time is referred to explicitly, while retaining its special notational and conceptual status.We examine this method by looking closely at two of the more influential formalisms featuring reified propositions, those of Allen and McDermott. We show that these do not have completely clear semantics, and that they make some unfortunate and unnecessary ontological commitments. Finally, we present a new formalism and demonstrate that it does not suffer from these disadvantages.     

Nonmonotonic reasoning,nonmonotonic logics and reasoning about change

In this paper we introduce nonmonotonic reasoning and the attempts at formalizing it using nonmonotonic logics. We examine and compare the best known of these. Despite the difference in motivation and technical construction there are strong similarities between these logics which are confirmed when they are finally shown to have a common basis. Finally we consider using nonmonotonic logics to represent reasoning about change.     

On the correspondence between abstract dialectical frameworks and nonmonotonic conditional logics

Annals of Mathematics and Artificial Intelligence - The exact relationship between formal argumentation and nonmonotonic logics is a research topic that keeps on eluding researchers despite recent...     

Operational concepts of nonmonotonic logics part 1: Default logic

We give an introduction to default logic, one of the most prominent nonmonotonic logics. Emphasis is given to providing an operational interpretation for the semantics of default logic that is usually defined by fixed-point concepts (extensions). We introduce a process model that allows to exactly calculate the extensions of a default theory in a quite easy way. We give a prototypical implementation of processes in Prolog able to handle the examples that can be found in literature. Finally, we develop some theoretical results about default logic and give new simple proofs using the process model as a theoretical tool.     

Sequent calculi for skeptical reasoning in predicate default logic and other nonmonotonic logics

Sequent calculi for skeptical consequence in predicate default logic, predicate stable model logic programming, and infinite autoepistemic theories are presented and proved sound and complete. While skeptical consequence is decidable in the finite propositional case of all three formalisms, the move to predicate or infinite theories increases the complexity of skeptical reasoning to being ₁¹-complete. This implies the need for sequent rules with countably many premises, and such rules are employed. AMS subject classification 03B42, 68N17, 68T27This paper grew directly out of the authors dissertation, written under the direction of Anil Nerode.     

An AGM-style belief revision mechanism for probabilistic spatio-temporal logics

There is now extensive interest in reasoning about moving objects. A probabilistic spatio-temporal (PST) knowledge base (KB) contains atomic statements of the form “Object o is/was/will be in region r at time t with probability in the interval [?,u]”. In this paper, we study mechanisms for belief revision in PST KBs. We propose multiple methods for revising PST KBs. These methods involve finding maximally consistent subsets and maximal cardinality consistent subsets. In addition, there may be applications where the user has doubts about the accuracy of the spatial information, or the temporal aspects, or about the ability to recognize objects in such statements. We study belief revision mechanisms that allow changes to the KB in each of these three components. Finally, there may be doubts about the assignment of probabilities in the KB. Allowing changes to the probability of statements in the KB yields another belief revision mechanism. Each of these belief revision methods may be epistemically desirable for some applications, but not for others. We show that some of these approaches cannot satisfy AGM-style axioms for belief revision under certain conditions. We also perform a detailed complexity analysis of each of these approaches. Simply put, all belief revision methods proposed that satisfy AGM-style axioms turn out to be intractable with the exception of the method that revises beliefs by changing the probabilities (minimally) in the KB. We also propose two hybrids of these basic approaches to revision and analyze the complexity of these hybrid methods.     

Justification logics, logics of knowledge, and conservativity

Several justification logics have been created, starting with the logic LP, (Artemov, Bull Symbolic Logic 7(1):1–36, 2001). These can be thought of as explicit versions of modal logics, or of logics of knowledge or belief, in which the unanalyzed necessity (knowledge, belief) operator has been replaced with a family of explicit justification terms. We begin by sketching the basics of justification logics and their relations with modal logics. Then we move to new material. Modal logics come in various strengths. For their corresponding justification logics, differing strength is reflected in different vocabularies. What we show here is that for justification logics corresponding to modal logics extending T, various familiar extensions are actually conservative with respect to each other. Our method of proof is very simple, and general enough to handle several justification logics not directly corresponding to distinct modal logics. Our methods do not, however, allow us to prove comparable results for justification logics corresponding to modal logics that do not extend T. That is, we are able to handle explicit logics of knowledge, but not explicit logics of belief. This remains open.     

Combining and automating classical and non-classical logics in classical higher-order logics

Numerous classical and non-classical logics can be elegantly embedded in Church??s simple type theory, also known as classical higher-order logic. Examples include propositional and quantified multimodal logics, intuitionistic logics, logics for security, and logics for spatial reasoning. Furthermore, simple type theory is sufficiently expressive to model combinations of embedded logics and it has a well understood semantics. Off-the-shelf reasoning systems for simple type theory exist that can be uniformly employed for reasoning within and about embedded logics and logics combinations. In this article we focus on combinations of (quantified) epistemic and doxastic logics and study their application for modeling and automating the reasoning of rational agents. We present illustrating example problems and report on experiments with off-the-shelf higher-order automated theorem provers.     

Including probabilistic target detection attributes into map representations

Range measuring sensors can play an extremely important role in robot navigation. All range measuring devices rely on a ‘detection criterion’ made in the presence of noise, to determine when the transmitted signal is considered detected and hence a range reading is obtained. In commonly used sensors, such as laser range finders and polaroid sonars, the criterion under which successful detection is assumed, is kept hidden from the user. However, ‘detection decisions’ on the presence of noise still take place within the sensor. This paper integrates signal detection probabilities into the map building process which provides the most accurate interpretation of such sensor data. To facilitate range detection analysis, map building with a frequency modulated continuous wave millimetre wave radar (FMCW MMWR), which is able to provide complete received power-range spectra for multiple targets down range is considered. This allows user intervention in the detection process and although not directly applicable to the commonly used ‘black-box’ type range sensors, provides insight as to how not only range values, but received signal strength values should be incorporated into the map building process.This paper presents two separate methods of map building with sensors which return both range and received signal power information. The first is an algorithm which uses received signal-to-noise power to make an estimates of the range to multiple targets down range, without any signal distribution assumptions. We refer to this as feature detection based on target presence probability (TPP). In contrast to the first method, the second method does use assumptions on the statistics of the signal in target presence and absence scenarios to formulate a probabilistic likelihood detector. This allows for an increased rate of convergence to ground truth. Evidence theory is then introduced to model and update successive observations in a recursive fashion. Both methods are then compared using real MMWR data sets from indoor and outdoor experiments.     

Default logic and specification of nonmonotonic reasoning

In this paper constructions leading to the formation of belief sets by agents are studied. The focus is on the situation when possible belief sets are built incrementally in stages. An infinite sequence of theories that represents such a process is called a reasoning trace. A set of reasoning traces describing all possible reasoning scenarios for the agent is called a reasoning frame. Default logic by Reiter is not powerful enough to represent reasoning frames. In the paper a generalization of default logic of Reiter is introduced by allowing infinite sets of justifications. This formalism is called infinitary default logic. In the main result of the paper it is shown that every reasoning frame can be represented by an infinitary default theory. A similar representability result for antichains of theories (belief frames) is also presented.     

Updates with Disjunctive Information: From Syntactical and Semantical Perspectives

The possible models approach is a classical minimal change semantics for knowledge base update, which provides an exclusive interpretation for disjunctive information in updates. It has been recognized that the exclusive interpretation for disjunction may be problematic under some circumstances. In this paper, we investigate inclusive interpretations for disjunctions in updates from both syntactical and semantical viewpoints. In particular, we propose two approaches for disjunctive update—the minimal change with exceptions (MCE) and the minimal change with maximal disjunctive inclusions (MCD). Both approaches provide inclusive interpretations for disjunctions in updates, though the first is syntax‐based and the second is model‐theoretic. We then characterize the MCE and MCD in terms of alternative minimal change criteria and relate them to traditional Katsuno and Mendelzon's update postulates.     

Social logics and expert systems

My goal is to emphasize the way we generally use the word logic and the sort of problems related to the definition of logic and the sort of problems related to the definition of logic. I also wish to underline the differences between human intelligence and artificial intelligence.I underline what, in my opinion, are the consequences for skill and knowledge transfer when using logic-based methodologies in landscapes deeply different from an input landscape. In this case I use, as a paradigm, the Indian way of logic, that has developed an original form of formal logic different from the Western logic.     

Reference and perspective in intuitionistic logics

What an intuitionist may refer to with respect to a given epistemic state depends not only on that epistemic state itself but on whether it is viewed concurrently from within, in the hindsight of some later state, or ideally from a standpoint “beyond” all epistemic states (though the latter perspective is no longer strictly intuitionistic). Each of these three perspectives has a different—and, in the last two cases, a novel—logic and semantics. This paper explains these logics and their semantics and provides soundness and completeness proofs. It provides, moreover, a critique of some common versions of Kripke semantics for intuitionistic logic and suggests ways of modifying them to take account of the perspective-relativity of reference.     

On the learning of rule uncertainties and their integration into probabilistic knowledge bases

We present a natural and realistic knowledge acquisition and processing scenario. In the first phase a domain expert identifies deduction rules that he thinks are good indicators of whether a specific target concept is likely to occur. In a second knowledge acquisition phase, a learning algorithm automatically adjusts, corrects and optimizes the deterministic rule hypothesis given by the domain expert by selecting an appropriate subset of the rule hypothesis and by attaching uncertainties to them. Then, in the running phase of the knowledge base we can arbitrarily combine the learned uncertainties of the rules with uncertain factual information.Formally, we introduce the natural class of disjunctive probabilistic concepts and prove that this class is efficiently distribution-free learnable. The distribution-free learning model of probabilistic concepts was introduced by Kearns and Schapire and generalizes Valiant's probably approximately correct learning model. We show how to simulate the learned concepts in probabilistic knowledge bases which satisfy the laws of axiomatic probability theory. Finally, we combine the rule uncertainties with uncertain facts and prove the correctness of the combination under an independence assumption.     

Concurrent program schemes and their logics

We define and investigate several classes of concurrent program schemes, including goto schemes and two versions of structured schemes, based on extensions of the regular expressions to trees. The schemes are studied on the first-order, Boolean-variable and propositional levels. We also define and study the dynamic logics based on these classes of schemes, including issues of decidability and axiomatization.