Reasoning about action and change

Reasoning about change is a central issue in research on human and robot planning. We study an approach to reasoning about action and change in a dynamic logic setting and provide a solution to problems which are related to the Frame problem. Unlike most work on the frame problem the logic described in this paper is monotonic. It (implicitly) allows for the occurrence of actions of multiple agents by introducing non-stationary notions of waiting and test. The need to state a large number of frame axioms is alleviated by introducing a concept of chronological preservation to dynamic logic. As a side effect, this concept permits the encoding of temporal properties in a natural way. We compare the relative merits of our approach and non-monotonic approaches as regards different aspects of the frame problem. Technically, we show that the resulting extended systems of propositional dynamic logic preserve (weak) completeness, finite model property and decidability.     

A Logic for Reasoning about Generic Judgments

This paper presents an extension of a proof system for encoding generic judgments, the logic FOλ^Δ of Miller and Tiu, with an induction principle. The logic FOλ^Δ is itself an extension of intuitionistic logic with fixed points and a “generic quantifier”, , which is used to reason about the dynamics of bindings in object systems encoded in the logic. A previous attempt to extend FOλ^Δ with an induction principle has been unsuccessful in modeling some behaviours of bindings in inductive specifications. It turns out that this problem can be solved by relaxing some restrictions on , in particular by adding the axiom B≡x.B, where x is not free in B. We show that by adopting the equivariance principle, the presentation of the extended logic can be much simplified. Cut-elimination for the extended logic is stated, and some applications in reasoning about an object logic and a simply typed λ-calculus are illustrated.     

Protected completions of first-order general logic programs

Minker and Perlis [15] have made the important observation that in certain circumstances, it might be desirable to prevent the inference of A when A is in the finite failure set of a logic program P. In this paper, we investigate the model-theoretic aspects of their proposal and develop a Fitting-style [5] declarative semantics for protected completions of general logic programs (containing function symbols). This extends the Minker-Perlis proposal which applies to function-free pure logic programs. In addition, an operational semantics is proposed and it is proven to be sound for existentially quantified positive queries and negative ground queries to general, canonical protected logic programs. Completeness issues are investigated and completeness is proved for positive existential queries and negative ground queries for the following classes of programs: (1) function-free general protected logic programs (the Minker-Perlis operational semantics apply to function-free pure protected logic programs), (2) pure protected logic programs (with function symbols) and (3) protected general logic programs that do not contain any internal variables (though they may contain function symbols).     

Multimodal linguistic inference

In this paper we compare grammatical inference in the context of simple and of mixed Lambek systems. Simple Lambek systems are obtained by taking the logic of residuation for a family of multiplicative connectives /,,\, together with a package of structural postulates characterizing the resource management properties of the connective.Different choices for Associativity and Commutativity yield the familiar logics NL, L, NLP, LP. Semantically, a simple Lambek system is a unimodal logic: the connectives get a Kripke style interpretation in terms of a single ternary accessibility relation modeling the notion of linguistic composition for each individual system.The simple systems earch have their virtues in linguistic analysis. But none of them in isolation provides a basis for a full theory of grammar. In the second part of the paper, we consider two types of mixed Lambek systems.The first type is obtained by combining a number of unimodal systems into one multimodal logic. The combined multimodal logic is set up in such a way that the individual resource management properties of the constituting logics are preserved. But the inferential capacity of the mixed logic is greater than the sum of its component parts through the addition of interaction postulates, together with the corresponding interpretive constraints on frames, regulating the communication between the component logics.The second type of mixed system is obtained by generalizing the residuation scheme for binary connectives to families of n-ary connectives, and by putting together families of different arities in one logic. We focus on residuation for unary connectives, and their combination with the standard binary vocabulary. The unary connectives play the role of control devices, both with respect to the static aspects of linguistic structure, and the dynamic aspects of putting this structure together. We prove a number of elementary logical results for unary families of residuated connectives and their combination with binary families, and situate existing proposals for structural modalities within a more general framework.An earlier version of the paper (under the title Residuation in mixed Lambek systems) was presented at the Deduction and Language workshop, London, March 1994, and the Rome workshop on Lambek Calculus, May 1994, and appeared in the IGPL Bulletin special issue Deduction and Language (Kempson (ed), Vol 3, 2–3). The materials in this paper prepare the ground for the sections on multiplicative connectives in a chapter on categorial grammar for the Handbook of Logic and Language (Van Benthem and ter Meulen (eds), Elsevier, to appear). I thank the editors of the Handbook and the audiences at these workshops for comments. I have greatly benefited from discussion, and joint work, with Natasha Kurtonina, Glyn Morrill and Dick Oehrle. All errors are my own.     

Defaults as restrictions on classical Hilbert-style proofs

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.Work carried out in the framework of the agreement between Italian PT Administration and FUBLaforia, Université Paris VI Pierre et Marie Curie, 4 Place Jussieu,Tour 46, 75252 Paris, France     

On a decidable generalized quantifier logic corresponding to a decidable fragment of first-order logic

Van Lambalgen (1990) proposed a translation from a language containing a generalized quantifierQ into a first-order language enriched with a family of predicatesR _i, for every arityi (or an infinitary predicateR) which takesQxg(x, y₁,..., y_n) to x(R(x, y₁,..., y₁) (x,y₁,...,y_n)) (y ₁,...,y_n are precisely the free variables ofQx). The logic ofQ (without ordinary quantifiers) corresponds therefore to the fragment of first-order logic which contains only specially restricted quantification. We prove that it is decidable using the method of analytic tableaux. Related results were obtained by Andréka and Németi (1994) using the methods of algebraic logic.     

Completeness of a combination of neighbourhood logic and temporal logic

This paper presents a completeness result, with respect to a possible world semantics, for a combination of a first-order temporal logic and neighbourhood logic. This logic was considered by Qiu and Zhou (1998, Proceedings of the PROCOMET 98, pp 444–461) to define semantics of a real-time OCCAM-like programming language.Received June 1999Accepted in revised form September 2003 by M. R. Hansen and C. B. Jones     

A modal contrastive logic: The logic of ‘but’

In this paper we present a modal approach to contrastive logic, the logic of contrasts as these appear in natural language conjunctions such as but. We use a simple modal logic, which is an extension of the well-knownS5 logic, and base the contrastive operators proposed by Francez in [2] on the basic modalities that appear in this logic. We thus obtain a logic for contrastive operators that is more in accord with the tradition of intensional logic, and that, moreover — we argue — has some more natural properties. Particularly, attention is paid to nesting contrastive operators. We show that nestings of but give quite natural results, and indicate how nestings of other contrastive operators can be done adequately. Finally, we discuss the example of the Hangman's Paradox and some similarities (and differences) with default reasoning. But but us no buts, as they say.Also partially supported by Nijmegen University, Toernooiveld, 6525 ED Nijmegen, The Netherlands.     

An O(nlog n)-SPACE Decision Procedure for the Propositional Dummett Logic

We present a tableau calculus for propositional Dummett logic, also known as LC (Linear Chain), where the depth of the deductions is linearly bounded by the length of the formulas to be proved. We then show that it is possible to decide propositional Dummett logic in O(nlogn)-SPACE.     

Querying datalog with arrays: Design and implementation issues

This paper deals with the implementation of logic queries where array structures are manipulated. Both top-down and bottom-up implementations of the presented logic language, called Datalog ^A , are considered. Indeed, SLD-resolution is generalized to realize Datalog ^A top-down query answering. Further, a fixpoint based evaluation of Datalog ^A queries is introduced, which forms the basis for efficient bottom-up implementation of queries obtained by generalizing rewriting techniques such as magic set method to the case of Datalog ^A programs.Work partially supported by a European Union grant under the EC-US project DEUS EX MACHINA: nondeterminism for deductive databases and by a MURST grant (40% share) under the project Sistemi formali e strumenti per basi di dati evolute.     

Local Logics, Non-Monotonicity and Defeasible Argumentation

In this paper we present an embedding of abstract argumentation systems into the framework of Barwise and Seligmans logic of information flow. We show that, taking P.M. Dungs characterization of argument systems, a local logic over states of a deliberation may be constructed. In this structure, the key feature of non-monotonicity of commonsense reasoning obtains as the transition from one local logic to another, due to a change in certain background conditions. Each of Dungs extensions of argument systems leads to a corresponding ordering of background conditions. The relations among extensions becomes a relation among partial orderings of background conditions. This introduces a conceptual innovation in Barwise and Seligmans representation of commonsense reasoning.     

Partial logics reconsidered: A conservative approach

Partial functions play an important role in computer science. In order to reason about partial functions one may extend classical logic to a logic supporting partial functions, a so-called partial logic. Usually such an extension necessitates side-conditions on classical proof rules in order to ensure consistency, and introduces non-classical proof rules in order to maintain completeness. These complications depend on the choice of consequence relation and non-monotonic operators. In computer science applications such complications are undesirable, because they affect (semi-) mechanical reasoning methods, and make manual reasoning difficult for computer scientists who are not logicians.By carefully choosing the consequence relation and non-monotonic operators, a simple calculus for partial functions arises. The resulting logic is healthy in the sense that meaningless formulas (such as top(emptystack) > 1) cannot be concluded, except from contradictory or false assumptions, and a meaningless assumption provides no information. This requires all axioms to be healthy; and as a consequence the excluded middle (a V ¬a) must be weakened (to meaningfula's). All the well-known classical rules preserve healthiness and are therefore sound in the logic, provided substitutions are restricted to meaningful terms. This means that program reasoning methods based on classical logic usually can be adapted to the presented partial logic.     

Applying fuzzy logic and genetic algorithms to enhance the efficacy of the PID controller in buffer overflow elimination for better channel response timeliness over the Internet

In this paper two novel intelligent buffer overflow controllers: the fuzzy logic controller (FLC) and the genetic algorithm controller (GAC) are proposed. In the FLC the extant algorithmic PID controller (PIDC) model, which combines the proportional (P), derivative (D) and integral (I) control elements, is augmented with fuzzy logic for higher control precision. The fuzzy logic divides the PIDC control domain into finer control regions. Every region is then defined either by a fuzzy rule or a ‘don't care’ state. The GAC combines the PIDC model with the genetic algorithm, which manipulates the parametric values of the PIDC as genes in a chromosome. The FLC and GAC operations are based on the objective function . The principle is that the controller should adaptively maintain the safety margin around the chosen reference point (represent by the ‘0’ of ) at runtime. The preliminary experimental results for the FLC and GAC prototypes indicate that they are both more effective and precise than the PIDC. After repeated timing analyses with the Intel's VTune Performer Analyzer, it was confirmed that the FLC can better support real‐time computing than the GAC because of its shorter execution time and faster convergence without any buffer overflow. Copyright © 2005 John Wiley & Sons, Ltd.     

A theory of nonmonotonic rule systems I

We introduce here the study of generalnonmonotonic rule systems. These deal with situations where a conclusion is drawn from a system of beliefsS (and seen to be inS), basedboth on some premises being inS and on some restraints not being inS. In the monotone systems of traditional logic there are no restraints, conclusions are drawn solely based on premises being inS. Nonmonotonic rule systems capture the essential syntactic, semantic, and algorithmic features of many nonmonotone systems such as default logic, negation as failure, truth maintenance, autoepistemic logic, and also important combinatorial questions from mathematics such as the marriage problem. This reveals semantics and syntax and proof procedures and algorithms for computing belief sets in many cases where none were previously available and entirely uniformly. In particular, we introduce and study deductively closed sets, extensions and weak extensions. Semantics of nonmonotonic rule systems is studied in part II of this paper and extensions to predicate classical, intuitionistic, and modal logics are left to a later paper.Work partially supported by NSF grant RII-8610671 and Kentucky EPSCoR program and ARO contract DAAL03-89-K-0124.Work partially supported by NSF grant DMS-8902797 and ARO contract DAAG629-85-C-0018.Work partially supported by NSF grant DMS-8702473.     

Timing Analysis of Combinational Circuits in Intuitionistic Propositional Logic

Classical logic has so far been the logic of choice in formal hardware verification. This paper proposes the application of intuitionistic logic to the timing analysis of digital circuits. The intuitionistic setting serves two purposes. The model-theoretic properties are exploited to handle the second-order nature of bounded delays in a purely propositional setting without need to introduce explicit time and temporal operators. The proof-theoretic properties are exploited to extract quantitative timing information and to reintroduce explicit time in a convenient and systematic way.We present a natural Kripke-style semantics for intuitionistic propositional logic, as a special case of a Kripke constraint model for Propositional Lax Logic (Information and Computation, Vol. 137, No. 1, 1–33, 1997), in which validity is validity up to stabilisation, and implication comes out as boundedly gives rise to. We show that this semantics is equivalently characterised by a notion of realisability with stabilisation bounds as realisers. Following this second point of view an intensional semantics for proofs is presented which allows us effectively to compute quantitative stabilisation bounds.We discuss the application of the theory to the timing analysis of combinational circuits. To test our ideas we have implemented an experimental prototype tool and run several examples.     

On the computational cost of disjunctive logic programming: Propositional case

This paper addresses complexity issues for important problems arising with disjunctive logic programming. In particular, the complexity of deciding whether a disjunctive logic program is consistent is investigated for a variety of well-known semantics, as well as the complexity of deciding whether a propositional formula is satisfied by all models according to a given semantics. We concentrate on finite propositional disjunctive programs with as well as without integrity constraints, i.e., clauses with empty heads; the problems are located in appropriate slots of the polynomial hierarchy. In particular, we show that the consistency check is ₂ ^p -complete for the disjunctive stable model semantics (in the total as well as partial version), the iterated closed world assumption, and the perfect model semantics, and we show that the inference problem for these semantics is ₂ ^p -complete; analogous results are derived for the answer sets semantics of extended disjunctive logic programs. Besides, we generalize previously derived complexity results for the generalized closed world assumption and other more sophisticated variants of the closed world assumption. Furthermore, we use the close ties between the logic programming framework and other nonmonotonic formalisms to provide new complexity results for disjunctive default theories and disjunctive autoepistemic literal theories.Parts of the results in this paper appeared in form of an abstract in the Proceedings of the Twelfth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-93), pp. 158–167. Other parts appeared in shortened form in the Proceedings of the International Logic Programming Symposium, Vancouver, October 1993 (ILPS-93), pp. 266–278. MIT Press.     

Towards a Logic for Performance and Mobility

Klaim is an experimental language designed for modeling and programming distributed systems composed of mobile components where distribution awareness and dynamic system architecture configuration are key issues. StocKlaim [R. De Nicola, D. Latella, and M. Massink. Formal modeling and quantitative analysis of KLAIM-based mobile systems. In ACM Symposium on Applied Computing (SAC). ACM Press, 2005. Also available as Technical Report 2004-TR-25; CNR/ISTI, 2004] is a Markovian extension of the core subset of Klaim which includes process distribution, process mobility, asynchronous communication, and site creation. In this paper, MoSL, a temporal logic for StocKlaim is proposed which addresses and integrates the issues of distribution awareness and mobility and those concerning stochastic behaviour of systems. The satisfiability relation is formally defined over labelled Markov chains. A large fragment of the proposed logic can be translated to action-based CSL for which efficient model-checkers exist. This way, such model-checkers can be used for the verification of StocKlaim models against MoSL properties. An example application is provided in the present paper.     

Condensed detachment is complete for relevance logic: A computer-aided proof

The condensed detachment ruleD is a combination of modus ponens with a minimal amount of substitution. EarlierD has been shown to be complete for intuitionistic and classical implicational logic but incomplete forBCK andBCI logic. We show thatD is complete for the relevance logic. One of the main steps is the proof of the formula ((a a) a) a found in interaction with our resolution theorem prover. Various strategies of generating consequences of the axioms and choosing best ones for the next iteration were tried until the proof was found.     

Logic programming and reasoning with incomplete information

The purpose of this paper is to expand the syntax and semantics of logic programs and disjunctive databases to allow for the correct representation of incomplete information in the presence of multiple extensions. The language of logic programs with classical negation, epistemic disjunction, and negation by failure is further expanded by new modal operators K and M (where for the set of rulesT and formulaF, KF stands for F is known to be true by a reasoner with a set of premisesT and MF means F may be believed to be true by the same reasoner). Sets of rules in the extended language will be called epistemic specifications. We will define the semantics of epistemic specifications (which expands the semantics of disjunctive databases from) and demonstrate their applicability to formalization of various forms of commonsense reasoning. In particular, we suggest a new formalization of the closed world assumption which seems to better correspond to the assumption's intuitive meaning.     

A logic for reasoning about time and reliability

We present a logic for stating properties such as, after a request for service there is at least a 98% probability that the service will be carried out within 2 seconds. The logic extends the temporal logic CTL by Emerson, Clarke and Sistla with time and probabilities. Formulas are interpreted over discrete time Markov chains. We give algorithms for checking that a given Markov chain satisfies a formula in the logic. The algorithms require a polynomial number of arithmetic operations, in size of both the formula and the Markov chain. A simple example is included to illustrate the algorithms.This paper is a revised and extended version of a paper that has appeared under the title A Framework for Reasoning about Time and Reliability in the Proceeding of the 10 ^th IEEE Real-time Systems Symposium, Santa Monica CA, December 1989. The work presented here was performed while the authors were employed by the Swedish Institute of Computer Science (SICS), and partially supported by the Swedish Board for Technical Development (ESPRIT/BRA project 3096, SPEC) and the Swedish Telecommunication Administration (project: PROCOM).