We consider some modal languages with a modal operator D whose semantics is based on the relation of inequality. Basic logical properties such as definability, expressive power and completeness are studied. Also, some connections with a number of other recent proposals to extend the standard modal language are pointed at.

We introduce a notion of bisimulation for graded modal logic. Using this notion, the model theory of graded modal logic can be developed in a uniform manner. We illustrate this by establishing the finite model property and proving invariance and definability results.

This paper is about a special version of PDL, proposed by Marcus Kracht, for reasoning about sibling ordered trees. It has four basic programs corresponding to the child, parent, left- and right-sibling relations in such trees. The original motivation for this language is rooted in the field of model-theoretic syntax. Motivated by recent developments in the area of semi-structured data, and, especially, in the field of query languages for XML (eXtensible Markup Language) documents, we revisit the language. This renewed interest (...) comes with a special focus on complexity and expressivity aspects of the language, aspects that have so far largely been ignored. We survey and derive complexity results, and spend most of the paper on the most important open question concerning the language: what is its expressive power? We approach this question from two angles: Which first-order properties can be expressed? And which second-order properties? While we are still some way from definitive answers to these questions, we discuss two first-order fragments of the PDL language for ordered trees, and show how the language can be used to express some typical (second-order) problems, like the boolean circuit and the frontier problem. (shrink)

For an arbitrary similarity type of Boolean Algebras with Operators we define a class of Sahlqvist identities. Sahlqvist identities have two important properties. First, a Sahlqvist identity is valid in a complex algebra if and only if the underlying relational atom structure satisfies a first-order condition which can be effectively read off from the syntactic form of the identity. Second, and as a consequence of the first property, Sahlqvist identities are canonical, that is, their validity is preserved under taking canonical (...) embedding algebras. Taken together, these properties imply that results about a Sahlqvist variety V van be obtained by reasoning in the elementary class of canonical structures of algebras in V. We give an example of this strategy in the variety of Cylindric Algebras: we show that an important identity called Henkin's equation is equivalent to a simpler identity that uses only one variable. We give a conceptually simple proof by showing that the firstorder correspondents of these two equations are equivalent over the class of cylindric atom structures. (shrink)

In many logics dealing with information one needs to make statements not only about cognitive states, but also about transitions between them. In this paper we analyze a dynamic modal logic that has been designed with this purpose in mind. On top of an abstract information ordering on states it has instructions to move forward or backward along this ordering, to states where a certain assertion holds or fails, while it also allows combinations of such instructions by means of operations (...) from relation algebra. In addition, the logic has devices for expressing whether in a given state a certain instruction can be carried out, and whether that state can be arrived at by carrying out a certain instruction. This paper deals mainly with technical aspects of our dynamic modal logic. It gives an exact description of the expressive power of this language; it also contains results on decidability for the language with 'arbitrary' structures and for the special case with a restricted class of admissible structures. In addition, a complete axiomatization is given. The paper concludes with a remark about the modal algebras appropriate for our dynamic modal logic, and some questions for further work. The paper only contains some sketchy examples showing how the logic can be used to capture situations of dynamic interest, far more detailed applications are given in a companion to this paper (De Rijke [33]). (shrink)

This modern, advanced textbook reviews modal logic, a field which caught the attention of computer scientists in the late 1970's.

We consider some modal languages with a modal operator $D$ whose semantics is based on the relation of inequality. Basic logical properties such as definability, expressive power and completeness are studied. Also, some connections with a number of other recent proposals to extend the standard modal language are pointed at.

For an arbitrary similarity type of Boolean Algebras with Operators we define a class ofSahlqvist identities. Sahlqvist identities have two important properties. First, a Sahlqvist identity is valid in a complex algebra if and only if the underlying relational atom structure satisfies a first-order condition which can be effectively read off from the syntactic form of the identity. Second, and as a consequence of the first property, Sahlqvist identities arecanonical, that is, their validity is preserved under taking canonical embedding algebras. (...) Taken together, these properties imply that results about a Sahlqvist variety V van be obtained by reasoning in the elementary class of canonical structures of algebras in V.We give an example of this strategy in the variety of Cylindric Algebras: we show that an important identity calledHenkin's equation is equivalent to a simpler identity that uses only one variable. We give a conceptually simple proof by showing that the first-order correspondents of these two equations are equivalent over the class of cylindric atom structures. (shrink)

In many logics dealing with information one needs to make statements not only about cognitive states, but also about transitions between them. In this paper we analyze a dynamic modal logic that has been designed with this purpose in mind. On top of an abstract information ordering on states it has instructions to move forward or backward along this ordering, to states where a certain assertion holds or fails, while it also allows combinations of such instructions by means of operations (...) from relation algebra. In addition, the logic has devices for expressing whether in a given state a certain instruction can be carried out, and whether that state can be arrived at by carrying out a certain instruction.This paper deals mainly with technical aspects of our dynamic modal logic. It gives an exact description of the expressive power of this language; it also contains results on decidability for the language with arbitrary structures and for the special case with a restricted class of admissible structures. In addition, a complete axiomatization is given. The paper concludes with a remark about the modal algebras appropriate for our dynamic modal logic, and some questions for further work. (shrink)

Modal Logic, originally conceived as the logic of necessity and possibility, has developed into a powerful mathematical and computational discipline. It is the main source of formal languages aimed at analyzing complex notions such as common knowledge and formal provability. Modal and modal-like languages also provide us with families of restricted description languages for relational and topological structures; they are being used in many disciplines, ranging from artificial intelligence, computer science and mathematics via natural language syntax and semantics to philosophy. (...) This volume presents a broad and up-to-date view of the field, with contributions covering both the foundations of modal logic itself and each of the aforementioned application areas. Complemented with an editorial introduction covering the roots of modal logic, this book is indispensable for any advanced student and researcher in non-classical logic and its applications. (shrink)

We introduce a notion of bisimulation for graded modal logic. Using this notion, the model theory of graded modal logic can be developed in a uniform manner. We illustrate this by establishing the finite model property and proving invariance and definability results.

Peirce algebras combine sets, relations and various operations linking the two in a unifying setting. This paper offers a modal perspective on Peirce algebras. Using modal logic a characterization of the full Peirce algebras is given, as well as a finite axiomatization of their equational theory that uses so-called unorthodox derivation rules. In addition, the expressive power of Peirce algebras is analyzed through their connection with first-order logic, and the fragment of first-order logic corresponding to Peirce algebras is described in (...) terms of bisimulations. (shrink)

We define bisimulations for temporal logic with Since and Until. This new notion is compared to existing notions of bisimulations, and then used to develop the basic model theory of temporal logic with Since and Until. Our results concern both invariance and definability. We conclude with a brief discussion of the wider applicability of our ideas.

Intensional logic has emerged, since the 1960' s, as a powerful theoretical and practical tool in such diverse disciplines as computer science, artificial intelligence, linguistics, philosophy and even the foundations of mathematics. The present volume is a collection of carefully chosen papers, giving the reader a taste of the frontline state of research in intensional logics today. Most papers are representative of new ideas and/or new research themes. The collection would benefit the researcher as well as the student. This book (...) is a most welcome addition to our series. The Editors CONTENTS PREFACE IX JOHAN VAN BENTHEM AND NATASHA ALECHINA Modal Quantification over Structured Domains PATRICK BLACKBURN AND WILFRIED MEYER-VIOL Modal Logic and Model-Theoretic Syntax 29 RUY J. G. B. DE QUEIROZ AND DOV M. GABBAY The Functional Interpretation of Modal Necessity 61 VLADIMIR V. RYBAKOV Logics of Schemes for First-Order Theories and Poly-Modal Propositional Logic 93 JERRY SELIGMAN The Logic of Correct Description 107 DIMITER VAKARELOV Modal Logics of Arrows 137 HEINRICH WANSING A Full-Circle Theorem for Simple Tense Logic 173 MICHAEL ZAKHARYASCHEV Canonical Formulas for Modal and Superintuitionistic Logics: A Short Outline 195 EDWARD N. ZALTA 249 The Modal Object Calculus and its Interpretation NAME INDEX 281 SUBJECT INDEX 285 PREFACE Intensional logic has many faces. In this preface we identify some prominent ones without aiming at completeness. (shrink)

In [6] Albert Visser shows that ILP completely axiomatizes all schemata about provability and relative interpretability that are provable in finitely axiomatized theories. In this paper we introduce a system called $\text{ILP}^{\omega}$ that completely axiomatizes the arithmetically valid principles of provability in and interpretability over such theories. To prove the arithmetical completeness of $\text{ILP}^{\omega}$ we use a suitable kind of tail models; as a byproduct we obtain a somewhat modified proof of Visser's completeness result.

This chapter contains sections titled: Introduction Model Theory Proof Theory Modal Predicate Logic.

We study several modal languages in which some (sets of) generalized quantifiers can be represented; the main language we consider is suitable for defining any first order definable quantifier, but we also consider a sublanguage thereof, as well as a language for dealing with the modal counterparts of some higher order quantifiers. These languages are studied both from a modal logic perspective and from a quantifier perspective. Thus the issues addressed include normal forms, expressive power, completeness both of modal systems (...) and of systems in the quantifier tradition, complexity as well as syntactic characterizations of special semantic constraints. Throughout the paper several techniques current in the theory of generalized quantifiers are used to obtain results in modal logic, and conversely. (shrink)

The idea of combining logics, structures, and theories has recently been attracting interest in areas as diverse as constraint logic programming, theorem proving, verification, computational linguistics, artificial intelligence and indeed, various branches of logic itself. It would be an exaggeration to claim that these (scattered, and by-and-large independent) investigations have crystallized into an enterprise meriting the title "combined methods"; nonetheless, a number of interesting themes are emerging. This introduction notes some prominent ones and relates them to the papers in this (...) special issue. (shrink)

The International workshop 'Frontiers of Combining Systems' is the only forum that is exclusively devoted to research efforts in this interdisciplinary area. This volume contains selected, edited papers from the second installment of the workshop. The contributions range from theorem proving, rewriting and logic to systems and constraints. While there is a clear emphasis on automated tools and logics, the contributions to this volume show that there exists a rapidly expanding body of solutions of particular instances of the combination problem, (...) and at the same time, that the issue of developing general frameworks for intergrating formalisms and systems is taking on an increasingly important position on the international research agenda. The idea of combining formal systems and algorithms has been attracting interest in areas as diverse as constraint logic programming, automated deduction, verification, information retrieval, computational linguistics, artificial intelligence, and logic. As any interesting real world system is a complex composite entity, decomposing its descriptive requirements (for design, verification, or maintenance purposes) into simpler, more restricted tasks is appealing as it is often the only plausible way of tackling complex modelling problems. A core body of notions, questions and results is beginning to emerge in the area, and we are beginning to understand the computational and logical impact of combining methods and algorithms. (shrink)

Combining logics has become a rapidly expanding enterprise that is inspired mainly by concerns about modularity and the wish to join together tailor made logical tools into more powerful but still manageable ones. A natural question is whether it offers anything new over and above existing standard languages. By analysing a number of applications where combined logics arise, we argue that combined logics are a potentially valuable tool in applied logic, and that endorsements of standard languages often miss the point. (...) Using the history of quantified modal logic as our main example, we also show that the use of combined structures and logics is a recurring theme in the analysis of existing logical systems. (shrink)

Modal logic originated in philosophy as the logic of necessity and possibility. Now it has reached a high level of mathematical sophistication and has many applications in a variety of disciplines, including theoretical and applied computer science, artificial intelligence, the foundations of mathematics, and natural language syntax and semantics. This volume represents the proceedings of the first international workshop on Advances in Modal Logic, held in Berlin, Germany, October 8-10, 1996. It offers an up-to-date perspective on the field, with contributions (...) covering its proof theory, its applications in knowledge representation, computing and mathematics, as well as its theoretical underpinnings. (shrink)

We examine the expressive power of probabilistic context free grammars (PCFGs), with a special focus on the use of probabilities as a mechanism for reducing ambiguity by filtering out unwanted parses. Probabilities in PCFGs induce an ordering relation among the set of trees that yield a given input sentence. PCFG parsers return the trees bearing the maximum probability for a given sentence, discarding all other possible trees. This mechanism is naturally viewed as a way of defining a new class of (...) tree languages. We formalize the tree language thus defined, study its expressive power, and show that the latter is beyond context freeness. While the increased expressive power offered by PCFGs helps to reduce ambiguity, we show that, in general, it cannot be decided whether a PCFG removes all ambiguities. (shrink)

This is an exploratory paper about combining logics, combining theories and combining structures. Typically when one applies logic to such areas as computer science, artificial intelligence or linguistics, one encounters hybrid ontologies. The aim of this paper is to identify plausible strategies for coping with ontological richness.

This is an exploratory paper about combining logics, combining theories and combining structures. Typically when one applies logic to such areas as computer science, artificial intelligence or linguistics, one encounters hybrid ontologies. The aim of this paper is to identify plausible strategies for coping with ontological richness.

In this paper back-and-forth structures are applied to the semantics of natural language. Back-and-forth structures consist of an event structure and an interval structure communicating via a relational link; transitions in the one structure correspond to transitions in the other. Such entities enable us to view temporal constructions (such as tense, aspect, and temporal connectives) as methods of moving systematically between information sources. We illustrate this with a treatment of the English present perfect, and progressive aspect, that draws on ideas (...) developed in Moens & Steedman (1988), and discuss the role of rich ontologies in formal semantics. (shrink)