Logic for Concurrency and Synchronisation

ISBN-13: 9781402012709 / Angielski / Twarda / 2003 / 285 str.

Ruy J. G. B. de Queiroz; Ruy J. G. B. De Ed Queiroz; R. J. de Queiroz

Opis

The study of information-based actions and processes has been a vibrant - terface between logic and computer science for several decades now. Indeed, several natural perspectives come together here. On the one hand, logical s- tems may be used to describe the dynamics of arbitrary computational p- cesses - as in the many sophisticated process logics available today. But also, key logical notions such as model checking or proof search are themselves informational processes involving agents with goals. The interplay between these descriptive and dynamic aspects shows even in our ordinary language. A word like "proof" hdenotes both a static 'certificate' of truth, and an activity which humans or machines engage in. Increasing our understanding of l- ics of this sort tells us something about computer science, and about cognitive actions in general. The individual chapters of this book show the state of the art in current - vestigations of process calculi such as linear logic, and - with mainly two major paradigms at work, namely, linear logic and modal logic. These techniques are applied to the title themes of concurrency and synchronisation, but there are also many repercussions for topics such as the geometry of proofs, categorial semantics, and logics of graphs. Viewed - gether, the chapters also offer exciting glimpses of future integration, as the reader moves back and forth through the book.

Spis treści

List of Figures. List of Tables. Foreword; J. van Benthem. Preface. Contributing Authors. I: From a Structural Perspective. 1. Geometry of Deduction via Graphs of Proofs; A. Grisi de Oliveira, R.J.B.G. Queiroz. 1. Motivation. 2. The idea of stuying proofs as geometric objects. 3. Proof-nets. 4. Logical flow graphs. 5. Multiple-conclusion classical calculi. 6. Finale. 2. Chu's Construction: A Proof-Theoretic Approach; G. Bellin. 1. Preface. 2. The trip translation. 3. Chu's construction. 4. Proof-nets, trips and translations. 3. Two Paradigms of Logical Computation in Affine Logic? G. Bellin. 1. Introduction. 2. Sequent calculus of MAL + Mix. 3. Additive mix. 4. Proof-nets for MAL + Mix. 5. Cut-elimination modulo irrelevance. 6. Symmetric reductions require Mix. 4. Proof Systems for pi-Calculus Logics; M. Dam. 1. Introduction. 2. Preliminaries on the pi-calculus. 3. A pi-mu-calculus. 4. Example specifications. 5. Proof system, modal fragment. 6. Soundness and completeness for the modal fragment. 7. Proof rules for recursive formulas. 8. Finite control completeness. 9. Natural numbers. 10. Buffers. 11. Conclusion. II: From a Descriptive Perspective. 5. A Tutorial Introduction to Symbolic Model Checking; D. Déharbe. 1. Introduction. 2. Kripke structures. 3. Temporal logic model checking.4. Symbolic model checking. 5. Loopless undirected graphs. 6. Modal definability. 7. k-Colourable graphs. 8. Conclusions. 7. Bisimulation and Language Equivalence; C. Stirling. 1. Introduction. 2. Background. 3. Caucal's hierarchy. 4. Richer logics. 5. Finite model theory.