Semantical investigations into nonmonotonic and probabilistic logics

Different forms of semantics have been proposed for conditionals of the form “Usually, if A then B”, ranging from quantitative probability distributions to qualitative approaches using plausibility orderings, possibility distributions, or conditional objects. Atomic-bound systems, also called big-stepped probabilities, allow qualitative reasoning with probabilities, aiming at bridging the gap between qualitative and quantitative argumentation and providing a model for the nonmonotonic reasoning system P. By using Goguen and Burstall’s notion of institutions for the formalization of logical systems, we elaborate precisely which formal connections exist among big-stepped probabilities, standard probabilities, and qualitative logics. Based on our investigations, we also develop two variants of conditional objects, one of them having a simpler semantics while still providing a model for system P.     

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.     

A functional correspondence between call-by-need evaluators and lazy abstract machines

We bridge the gap between compositional evaluators and abstract machines for the lambda-calculus, using closure conversion, transformation into continuation-passing style, and defunctionalization of continuations. This article is a followup of our article at PPDP 2003, where we consider call by name and call by value. Here, however, we consider call by need.We derive a lazy abstract machine from an ordinary call-by-need evaluator that threads a heap of updatable cells. In this resulting abstract machine, the continuation fragment for updating a heap cell naturally appears as an ‘update marker’, an implementation technique that was invented for the Three Instruction Machine and subsequently used to construct lazy variants of Krivine's abstract machine. Tuning the evaluator leads to other implementation techniques such as unboxed values. The correctness of the resulting abstract machines is a corollary of the correctness of the original evaluators and of the program transformations used in the derivation.     

On the relationship between annotated logic programs and nonmonotonic formalisms

Abstract

In the past we developed a semantics for a restricted annotated logic language for inheritance reasoning. Here we generalize it to annotated Horn logic programs. We first provide a formal account of the language, describe its semantics, and provide an interpreter written in Prolog for it. We then investigate its relationship to Belnap's 4-valued logic, Gelfond and Lifschitz's semantics for logic programs with negation, Brewka's prioritized default logics and other annotated logics due to Kifer et al.     

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.     

Embedding and automating conditional logics in classical higher-order logic

A sound and complete embedding of conditional logics into classical higher-order logic is presented. This embedding enables the application of off-the-shelf higher-order automated theorem provers and model finders for reasoning within and about conditional logics.     

On the correspondence between AVL trees and brother trees

We discuss the relationships of the classes of height-balanced (search) trees and the classes of brother (search) trees. In particular we characterize each class of height-balanced trees in terms of the class of “corresponding” brother trees and vice versa. Secondly, we show how this characterization leads to the notion of nonstandard updating algorithms. We derive a nonstandard insertion algorithm for height-balanced search trees to illustrate the notion. Finally we consider something of the similarities and differences between the standard and nonstandard insertion algorithms for height-balanced search rees.     

On nonmonotonic reasoning with the method of sweeping presumptions

Reasoning almost always occurs in the face of incomplete information. Such reasoning is nonmonotonic in the sense that conclusions drawn may later be withdrawn when additional information is obtained. There is an active literature on the problem of modeling such nonmonotonic reasoning, yet no category of method-let alone a single method-has been broadly accepted as the right approach. This paper introduces a new method, called sweeping presumptions, for modeling nonmonotonic reasoning. The main goal of the paper is to provide an example-driven, nontechnical introduction to the method of sweeping presumptions, and thereby to make it plausible that sweeping presumptions can usefully be applied to the problems of nonmonotonic reasoning. The paper discusses a representative sample of examples that have appeared in the literature on nonmonotonic reasoning, and discusses them from the point of view of sweeping presumptions.     

A logic of argumentation for specification and verification of abstract argumentation frameworks

In this paper, we propose a logic of argumentation for the specification and verification (LA4SV) of requirements on Dung??s abstract argumentation frameworks. We distinguish three kinds of decision problems for argumentation verification, called extension verification, framework verification, and specification verification respectively. For example, given a political requirement like ??if the argument to increase taxes is accepted, then the argument to increase services must be accepted too,?? we can either verify an extension of acceptable arguments, or all extensions of an argumentation framework, or all extensions of all argumentation frameworks satisfying a framework specification. We introduce the logic of argumentation verification to specify such requirements, and we represent the three verification problems of argumentation as model checking and theorem proving properties of the logic. Moreover, we recast the logic of argumentation verification in a modal framework, in order to express multiple extensions, and properties like transitivity and reflexivity of the attack relation. Finally, we introduce a logic of meta-argumentation where abstract argumentation is used to reason about abstract argumentation itself. We define the logic of meta-argumentation using the fibring methodology in such a way to represent attack relations not only among arguments but also among attacks. We show how to use this logic to verify the requirements of argumentation frameworks where higher-order attacks are allowed [A preliminary version of the logic of argumentation compliance was called the logic of abstract argumentation?(2005).]     

On the formal semantics of IF-like logics

In classical logics, the meaning of a formula is invariant with respect to the renaming of bound variables. This property, normally taken for granted, has been shown not to hold in the case of Independence Friendly (IF) logics. In this paper we argue that this is not an inherent characteristic of these logics but a defect in the way in which the compositional semantics given by Hodges for the regular fragment was generalized to arbitrary formulas. We fix this by proposing an alternative formalization, based on a variation of the classical notion of valuation. Basic metatheoretical results are proven. We present these results for Hodges' slash logic (from which these can be easily transferred to other IF-like logics) and we also consider the flattening operator, for which we give novel game-theoretical semantics.     

Dualities between alternative semantics for logic programming and nonmonotonic reasoning

The Gelfond-Lifschitz operator associated with a logic program (and likewise the operator associated with default theories by Reiter) exhibits oscillating behavior. In the case of logic programs, there is always at least one finite, nonempty collection of Herbrand interpretations around which the Gelfond-Lifschitz operator bounces around. The same phenomenon occurs with default logic when Reiter's operator is considered. Based on this, a stable class semantics and extension class semantics has been proposed. The main advantage of this semantics was that it was defined for all logic programs (and default theories), and that this definition was modelled using the standard operators existing in the literature such as Reiter's operator. In this paper our primary aim is to prove that there is a very interestingduality between stable class theory and the well-founded semantics for logic programming. In the stable class semantics, classes that were minimal with respect to Smyth's power-domain ordering were selected. We show that the well-founded semantics precisely corresponds to a class that is minimal w.r.t. Hoare's power domain ordering: the well-known dual of Smyth's ordering. Besides this elegant duality, this immediately suggests how to define a well-founded semantics for default logic in such a way that the dualities that hold for logic programming continue to hold for default theories. We show how the same technique may be applied to strong autoepistemic logic: the logic of strong expansions proposed by Marek and Truszczynski.     

The relationship between KLM and MAK models for nonmonotonic inference operations

The purpose of this note is to make quite clear the relationship between two variants of the general notion of a preferential model for nonmonotonic inference: the models of Kraus, Lehmann and Magidor (KLM models) and those of Makinson (MAK models). On the one hand, we introduce the notion of the core of a KLM model, which suffices to fully determine the associated nonmonotonic inference relation. On the other hand, we slightly amplify MAK models with a monotonic consequence operation as additional ingredient. We give two equivalent characterizations of the cores of KLM models: they are precisely the amplified MAK models whose satisfaction relation:

may be expressed as the intersection of some non-empty family of satisfaction relations each of which is classically well-behaved; or

satisfies certain syntactic conditions.

This gives corollary characterizations of certain particular classes of KLM models, notably those that are (in their terminology) cumulative and more specifically those they call preferential.     

On the complexity of entailment in propositional multivalued logics

Multivalued logics have a long tradition in the philosophy and logic literature that originates from the work by ukaszewicz in the 1920s. More recently, many AI researchers have been interested in this topic for both semantic and computational reasons. Multivalued logics have indeed been frequently used both for their semantic properties and as tools for designing tractable reasoning systems. We focus here on the computational aspects of multivalued logics. The main result of this paper is a detailed picture of the impact that the semantic definition, the synthactic form and the assumptions on the relative sizes of the inputs have on the complexity of entailment checking. In particular we show new polynomial cases and generalize polynomial cases already known in the literature for various popular multivalued logics. Such polynomial cases are obtained by means of two simple algorithms, sharing a common method.     

On the equivalence between small-step and big-step abstract machines: a simple application of lightweight fusion

We show how Ohori and Sasano's recent lightweight fusion by fixed-point promotion provides a simple way to prove the equivalence of the two standard styles of specification of abstract machines: (1) in small-step form, as a state-transition function together with a ‘driver loop’, i.e., a function implementing the iteration of this transition function; and (2) in big-step form, as a tail-recursive function that directly maps a given configuration to a final state, if any. The equivalence hinges on our observation that for abstract machines, fusing a small-step specification yields a big-step specification. We illustrate this observation here with a recognizer for Dyck words, the CEK machine, and Krivine's machine with call/cc.The need for such a simple proof is motivated by our current work on small-step abstract machines as obtained by refocusing a function implementing a reduction semantics (a syntactic correspondence), and big-step abstract machines as obtained by CPS-transforming and then defunctionalizing a function implementing a big-step semantics (a functional correspondence).     

论高等教育终身化和大众化的辩证关系

通过对高等学校的功能的分析,指出高等教育的大众化和终身化是现代高等教育的两大趋势,二者是辩证统一的关系.构建学习化社会;提高全民素质;实现人的全面发展是高等教育大众化和终身化的共同目标.成人高等教育是实现高等教育大众化和终身化辩证统一的关键性环节.