Multi-Dimensional Modal Logic - Maarten Marx

. .

Résumé :
Modal Logic is a branch of logic with applications in many related disciplines such as computer science, philosophy, linguistics and artificial intelligence. Over the last twenty years, in all of these neighbouring fields, modal systems have been developed that we call multi-dimensional. (Our definition of multi-dimensionality in modal logic is a technical one: we call a modal formalism multi-dimensional if, in its intended semantics, the universe of a model consists of states that are tuples over some more basic set.) This book treats such multi-dimensional modal logics in a uniform way, linking their mathematical theory to the research tradition in algebraic logic. We will define and discuss a number of systems in detail, focusing on such aspects as expressiveness, definability, axiomatics, decidability and interpolation. Although the book will be mathematical in spirit, we take care to give motivations from the disciplines mentioned earlier on.

Biographie:
Erich Graedel is a Professor of Mathematical Foundations of Computer Science at the University of Technology Aachen. His research interests include algorithms, complexity, and logic in computer science. Phokion G. Kolaitis is a professor of computer science at the University of California, Santa Cruz. His current research interests include logic in computer science, computational complexity, and database theory. He earned a Diploma in Mathematics from the University of Athens, Greece in 1973, and a Ph.D. in Mathematics from the University of California, Los Angeles in 1978. Before joining UC Santa Cruz in 1988, he served as an L.E. Dickson Instructor of Mathematics at the University of Chicago, a faculty member at Occidental College, a visiting faculty member at Stanford University, and a visiting scientist at the IBM Almaden Research Center. Kolaitis was awarded a Guggenheim Fellowship during 1993-94. In 1995, he received an Excellence in Teaching Award by the graduating computer science and computer engineering students at UC Santa Cruz. Leonid Libkin received his PhD from the University of Pennsylvania and is currently Professor of Computer Science at the University of Toronto. His main research interests include databases and applications of logic in computer science. Maarten Marx is an associate professor at the Vrije Universiteit Amsterdam. His research interests are in modal and algebraic logic. Joel Spencer is a Professor of Mathematics and Computer Scienceat the Courant Institute, New York University. His research interests lie in interface between Discrete Mathematics and Theoretical Computer Science, most particularly with the Probabilistic Method as developed by Paul Erdos. Moshe Y. Vardi is a Noah Harding Professor of Computer Science and Chair of Computer Science at Rice University. Prior to joining Rice in 1993, he was at the IBM Almaden Research Center, where he managed the Mathematics and Related Computer Science Department. His research interests include database systems, computational-complexity theory, multi-agent systems, and design specification and verification. Vardi received his Ph.D. from the Hebrew University of Jerusalem in 1981. He is the author and co-author of over 120 technical papers, as well as a book titled Reasoning about Knowledge. Vardi is the recipient of 3 IBM Outstanding Innovation Awards. He is an editor of several international journals and is a Fellow of the Association of Computing Machinery. Yde Venema studied mathematics...

Sommaire:
1 Multi-dimensional modal logic.- 1.1 What is multi-dimensional modal logic?.- 1.2 Manifestations of multi-dimensional modal logics.- 1.3 Themes and questions.- 1.4 Overview of the book.- 1.5 How to read this book.- 2 Two-dimensional modal logics.- 2.1 Operations on the square universe.- 2.2 Axiomatizing S5-square.- 2.3 Cylindric modal logic of squares.- 2.4 The modal logic of composition.- 2.5 A two-dimensional temporal logic.- 2.6 Historical notes.- 3 Arrow logic.- 3.1 Introduction.- 3.2 Motivation.- 3.3 Arrow logic and relation algebras.- 3.4 Connection with first order logic.- 3.5 Characterizing (local) squares.- 3.6 Axiomatizing (local) squares.- 3.7 Decidability and interpolation.- 3.8 Temporal arrow logic.- 3.9 Other directions in arrow logic.- 4 Modal logics of intervals.- 4.1 Introduction.- 4.2 The System HS: Introduction.- 4.3 The system HS: expressiveness.- 4.4 The System HS: Axiomatics.- 5 Modal logics of relations.- 5.1 Introduction.- 5.2 Modalizing first-order logic.- 5.3 Abstract and generalized assignment frames.- 5.4 Characterizing cubes and local cubes.- 5.5 Meta-properties.- 5.6 Infinite dimensions.- 5.7 Connections.- 6 Multi-dimensional semantics for every modal language.- 6.1 Logics with one modality.- 6.2 Logics with arbitrary many modalities.- 6.3 Versatile similarity types.- 6.4 The modal logic of composition and its conjugates.- Open problems.- Appendices.- A Modal Similarity Types.- A.1 Introduction.- A.2 Modal similarity types.- A.3 Frames, models and correspondence.- A.4 Structural frame operations.- A.5 Boolean S-algebras.- A.6 Frames and algebras.- A.7 Modal logics and derivation systems.- A.8 Algebraic derivations.- A.9 Canonical structures.- B A Modal Toolkit.- B.1 Sahlqvist theory.- B.1.1 Definitions.- B.1.2 Sahlqvist correspondence.- B.1.3 Canonicity & completeness.- B.1.4 Algebraic aspects of Sahlqvist theory.- B.2 Logical operators.- B.2.1 The universal modality.- B.2.2 Versatile similarity types.- B.2.3 The D-operator.- B.3 Negative definability and unorthodox axiomatics.- B.4 Interpolation.- B.5 Filtrations.- B.6 A local and a global paradigm.- List of symbols.