Ebook: Theory and Formal Methods 1993: Proceedings of the First Imperial College Department of Computing Workshop on Theory and Formal Methods, Isle of Thorns Conference Centre, Chelwood Gate, Sussex, UK, 29–31 March 1993

This volume contains the proceedings of the fIrst workshop held by the Theory and Formal Methods Section ofthe Imperial College Department of Computing. It contains papers from almost every member of the Section, from our long-term academic visitors, and from those who have recently left us. The papers fall into four broad areas: • semantics • concurrency • logic • specification with some papers spanning a number of disciplines. The subject material varies from work on mathematical foundations to practical applications of this theory, expressing the Section's commitment to both the foundations of computer science, and the application of theory to real computing problems. In preparing the workshop and these proceedings, care was taken to ensure that there were papers overviewing a field, as well as ones whose primary aim was to present new scientifIc results. This had a dual purpose: to bring our Section members up to speed in some of the areas being worked on by the Section; and to provide the reader of the proceedings not only with a good introduction to many of the specifIc areas being investigated by the Section, but also with details of some of our latest results. All the papers presented at the workshop were revised following comments made by the workshop participants, and all were subsequently reviewed by at least two people before producing the fInal versions contained in this volume.

---

The Theory and Formal Methods Section of the Imperial College Department of Computing has an international reputation for research into the foundations of computer science, and the application of this theory to real computing problems. In March 1993 it held the first in a proposed series of workshops on theory and formal methods at the Isle of Thorns Conference Centre in Sussex, UK. Almost every member of the section contributed to the workshop, thereby providing comprehensive coverage of the work being done by this important research group. This volume contains revised versions of the papers presented at the workshop. They cover four main areas - semantics, concurrency, logic, and specification - with some papers spanning a variety of disciplines. The papers fall into two main categories: review papers which provide the reader with a good introduction to some of the specific areas being studied by the section, and research papers which give details of the latest results in these areas.

---

The Theory and Formal Methods Section of the Imperial College Department of Computing has an international reputation for research into the foundations of computer science, and the application of this theory to real computing problems. In March 1993 it held the first in a proposed series of workshops on theory and formal methods at the Isle of Thorns Conference Centre in Sussex, UK. Almost every member of the section contributed to the workshop, thereby providing comprehensive coverage of the work being done by this important research group. This volume contains revised versions of the papers presented at the workshop. They cover four main areas - semantics, concurrency, logic, and specification - with some papers spanning a variety of disciplines. The papers fall into two main categories: review papers which provide the reader with a good introduction to some of the specific areas being studied by the section, and research papers which give details of the latest results in these areas.
Content:
Front Matter....Pages i-viii
Front Matter....Pages 1-1
The Abstract Interpretation of Functional Languages....Pages 3-14
Deriving Category Theory from Type Theory....Pages 15-26
Graph Rewriting Systems and Abstract Interpretation....Pages 27-36
Geometric Logic in Computer Science....Pages 37-54
Front Matter....Pages 55-55
Interaction Categories....Pages 57-69
Animating LU....Pages 70-81
Dynamical systems, Measures and Fractals via Domain Theory....Pages 82-99
Self-duality, Minimal Invariant Objects and Karoubi Invariance in Information Categories....Pages 100-114
Reasoning About Gamma Programs....Pages 115-125
Generalising Interpretations Between Theories in the Context of (?-)institutions....Pages 126-147
Modelling Signal in Interaction Categories....Pages 148-158
Product Operations in Strong Monads....Pages 159-170
On the Equivalence of State-Transition Systems....Pages 171-182
Towards a Modal Logic of Durative Actions....Pages 183-194
Concurrency, Fairness and Logical Complexity....Pages 195-208
Concurrency and Conflict in CSP....Pages 209-225
A Complete Axiom System for CCS with a Stability Operator....Pages 226-234
An Internal Language for Autonomous Categories....Pages 235-246
Continuation Passing Transformation and Abstract Interpretation....Pages 247-259
A Note on Expressiveness of Process Algebra....Pages 260-264
Front Matter....Pages 55-55
Prioritising Preference Relations....Pages 265-275
Laws of Parallel Synchronised Termination....Pages 276-288
Implementing Process Calculi in C....Pages 289-301
An Exact Interpretation of while....Pages 302-313
Congruences for ?-respecting Formats of Rules....Pages 314-325
Back Matter....Pages 327-329

---

The Theory and Formal Methods Section of the Imperial College Department of Computing has an international reputation for research into the foundations of computer science, and the application of this theory to real computing problems. In March 1993 it held the first in a proposed series of workshops on theory and formal methods at the Isle of Thorns Conference Centre in Sussex, UK. Almost every member of the section contributed to the workshop, thereby providing comprehensive coverage of the work being done by this important research group. This volume contains revised versions of the papers presented at the workshop. They cover four main areas - semantics, concurrency, logic, and specification - with some papers spanning a variety of disciplines. The papers fall into two main categories: review papers which provide the reader with a good introduction to some of the specific areas being studied by the section, and research papers which give details of the latest results in these areas.
Content:
Front Matter....Pages i-viii
Front Matter....Pages 1-1
The Abstract Interpretation of Functional Languages....Pages 3-14
Deriving Category Theory from Type Theory....Pages 15-26
Graph Rewriting Systems and Abstract Interpretation....Pages 27-36
Geometric Logic in Computer Science....Pages 37-54
Front Matter....Pages 55-55
Interaction Categories....Pages 57-69
Animating LU....Pages 70-81
Dynamical systems, Measures and Fractals via Domain Theory....Pages 82-99
Self-duality, Minimal Invariant Objects and Karoubi Invariance in Information Categories....Pages 100-114
Reasoning About Gamma Programs....Pages 115-125
Generalising Interpretations Between Theories in the Context of (?-)institutions....Pages 126-147
Modelling Signal in Interaction Categories....Pages 148-158
Product Operations in Strong Monads....Pages 159-170
On the Equivalence of State-Transition Systems....Pages 171-182
Towards a Modal Logic of Durative Actions....Pages 183-194
Concurrency, Fairness and Logical Complexity....Pages 195-208
Concurrency and Conflict in CSP....Pages 209-225
A Complete Axiom System for CCS with a Stability Operator....Pages 226-234
An Internal Language for Autonomous Categories....Pages 235-246
Continuation Passing Transformation and Abstract Interpretation....Pages 247-259
A Note on Expressiveness of Process Algebra....Pages 260-264
Front Matter....Pages 55-55
Prioritising Preference Relations....Pages 265-275
Laws of Parallel Synchronised Termination....Pages 276-288
Implementing Process Calculi in C....Pages 289-301
An Exact Interpretation of while....Pages 302-313
Congruences for ?-respecting Formats of Rules....Pages 314-325
Back Matter....Pages 327-329
....