Dov Gabbay

This work is divided in two papers (Part I and Part II). In Part I, we study a class of polymodal logics (herein called the class of "Rare-logics") for which the set of terms indexing the modal operators are hierarchized in two levels: the set of Boolean terms and the set of terms built upon the set of Boolean terms. By investigating different algebraic properties satisfied by the models of the Rare-logics, reductions for decidability are established by faithfully translating the Rare-logics into more standard modal logics. The main idea of the translation consists in eliminating the Boolean terms by taking advantage of the components construction and in using various properties of the classes of semilattices involved in the semantics. The novelty of our approach allows us to prove new decidability results (presented in Part II), in particular for information logics derived from rough set theory and we open new perspectives to define proof systems for such logics (presented also in Part II).

The problem of interpolation is a classical problem in logic. Given a consequence relation |~ and two formulas φ and ψ with φ |~ ψ we try to find a “simple" formula α such that φ |~ α |~ ψ. “Simple" is defined here as “expressed in the common language of φ and ψ". Non-monotonic logics like preferential logics are often a mixture of a non-monotonic part with classical logic. In such cases, it is natural examine also variants of the interpolation problem, like: is there “simple" α such that φ ⊢ α |~ ψ where ⊢ is classical consequence? We translate the interpolation problem from the syntactic level to the semantic level. For example, the classical interpolation problem is now the question whether there is some “simple" model set X such that M(φ) ⫅ X ⫅ M(ψ). We can show that such X always exist for monotonic and antitonic logics. The case of non-monotonic logics is more complicated, there are several variants to consider, and we mostly have only partial results.

"This report investigates the question of the universality of classical logic. The approach is to show that an almost arbitrary logical system can be translated reasonably intuitively and almost automatically into classical logic. The path leading to this result goes through the analysis of what is reasonable logic, how to find semantics for it, how to build a labelled deductive system (LDS) for it, how to translate a LDS into classical logic and how to automate the process using SCAN. This report relies on other papers, published and/or to be published as explained in the acknowledgements.

We introduce Information Bearing Relation Systems (IBRS) as an abstraction of many logical systems. These are networks with arrows recursively leading to other arrows etc. We then define a general semantics for IBRS, and show that a special case of IBRS generalizes in a very natural way preferential semantics and solves open representation problems for weak logical systems. This is possible, as we can the strong coherence properties of preferential structures by higher arrows, that is, arrows, which do not go to points, but to arrows themselves

The paper presents a compositional approach to the verification of CTL* properties over reactive systems. Both symbolic model-checking and deductive verification are considered. Both methods are based on two decomposition principles. A general state formula is decomposed into basic state formulas which are CTL* formulas with no embedded path quantifiers. To deal with arbitrary basic state formulas, we introduce another reduction principle which replaces each basic path formula, i.e., path formulas whose principal operator is temporal and which contain no embedded temporal operators or path quantifiers, by a newly introduced boolean variable which is added to the system. Thus, both the algorithmic and the deductive methods are based on two statification transformations which successively replace temporal formulas by assertions which contain no path quantifiers or temporal operators. Performing these decompositions repeatedly, we remain with basic assertional formulas, i.e., formulas of the form Efp and Afp for some assertion p. In the model-checking method we present a single symbolic algorithm to verify both universal and existential basic assertional properties. In the deductive method we present a small set of proof rules and show that this set is sound and relatively complete for verifying universal and existential basic assertional properties over reactive systems. Together with two proof rules for the decompositions, we obtain a sound and relatively complete proof system for arbitrary CTL* properties. Interestingly, the deductive approach for CTL* presented here, offers a viable new approach to the deductive verification of arbitrary LTL formulas. The paper corrects a previous preliminary version of a deductive system for CTL*, in which some of the rules were unsound. The correction is based on the introduction of a new type of temporal testers which are guaranteed to be non blocking. That is, when composed with a deadlock-free system, which is a key operation in the verification process, the resulting composed system is guaranteed to remain deadlock free

Axiomatizations are presented for fuzzy logics characterized by uninorms continuous on the half-open real unit interval [0,1), generalizing the continuous t-norm based approach of Hájek. Basic uninorm logic BUL is defined and completeness is established with respect to algebras with lattice reduct [0,1] whose monoid operations are uninorms continuous on [0,1). Several extensions of BUL are also introduced. In particular, Cross ratio logic CRL, is shown to be complete with respect to one special uninorm. A Gentzen-style hypersequent calculus is provided for CRL and used to establish co-NP completeness results for these logics.

We develop a logical modelling approach to describe evolvable computational systems. In this account, evolvable systems are built hierarchically from components where each component may have an associated supervisory process. The supervisor's purpose is to monitor and possibly change its associated component. Evolutionary change may be determined purely internally from observations made by the supervisor or may be in response to external change. Supervisory processes may be present at any level in the component hierarchy allowing us to use evolutionary behaviour as an integral part of system design. We model such systems in a revision-based first-order logical framework in which supervisors are modelled as theories which are at a logical meta-level to the theories of their components. This enables evolutionary change of the component to be induced by revision-based changes of the supervisor at the meta-level. In this way, the intervention required in evolutionary change is modelled purely logically. The hierarchical component-based structure is fairly intricate so we present the basic ideas firstly in a simple setting, the well-known blocks world, before introducing tree-based structures to represent component hierarchies. We also introduce some techniques for establishing the behaviour of evolvable systems specified in this logical framework. The ideas and concepts are driven by example throughout. We conclude with a more substantial example, that of a simple model of an evolvable system of automated bank teller machines

The Babylonian Talmud, compiled from the 2nd to 7th centuries C.E., is the primary source for all subsequent Jewish laws. It is not written in apodeictic style, but rather as a discursive record of (real or imagined) legal (and other) arguments crossing a wide range of technical topics. Thus, it is not a simple matter to infer general methodological principles underlying the Talmudic approach to legal reasoning. Nevertheless, in this article, we propose a general principle that we believe helps to explain the variety of methods used by the Rabbis of the Talmud for resolving uncertainty in matters of Jewish Law (henceforth: Halakhah). Such uncertainty might arise either if the facts of a case are clear but the relevant law is debatable or if the facts themselves are unclear

This paper gives a simple method for providing categorial brands of feature-based unification grammars with a model-theoretic semantics. The key idea is to apply the paradigm of fibred semantics (or layered logics, see Gabbay (1990)) in order to combine the two components of a feature-based grammar logic. We demonstrate the method for the augmentation of Lambek categorial grammar with Kasper/Rounds-style feature logic. These are combined by replacing (or annotating) atomic formulas of the first logic, i.e. the basic syntactic types, by formulas of the second. Modelling such a combined logic is less trivial than one might expect. The direct application of the fibred semantics method where a combined atomic formula like np (num: sg & pers: 3rd) denotes those strings which have the indicated property and the categorial operators denote the usual left- and right-residuals of these string sets, does not match the intuitive, unification-based proof theory. Unification implements a global bookkeeping with respect to a proof whereas the direct fibring method restricts its view to the atoms of the grammar logic. The solution is to interpret the (embedded) feature terms as global feature constraints while maintaining the same kind of fibred structures. For this adjusted semantics, the anticipated proof system is sound and complete.

ABSTRACT A propositional temporal logic is introduced whose operators quantify over intervals of a reference time line. The intervals are specified symbolically, for example ?next week's weekend?. The specification language for the intervals takes into account all the features of real calendar systems. A simple statement which can be expressed in this language is for example: ?yesterday I worked for eight hours with one hour lunch break at noon?. Calendar Logic can be translated into propositional logic. Satisfiability is therefore decidable. Since the translation is exponential, a tableau decision procedure for checking decidability is presented as an alternative

In this article, we propose a belief revision approach for families of (non-classical) logics whose semantics are first-order axiomatisable. Given any such (non-classical) logic , the approach enables the definition of belief revision operators for , in terms of a belief revision operation satisfying the postulates for revision theory proposed by Alchourrrdenfors and Makinson (AGM revision, Alchourrukasiewicz's many-valued logic. In addition, we present a general methodology to translate algebraic logics into classical logic. For the examples provided, we analyse in what circumstances the properties of the AGM revision are preserved and discuss the advantages of the approach from both theoretical and practical viewpoints