Recent Trends in Algebraic Development Techniques: 13th International Workshop, WADT'98 Lisbon, Portugal, April 2-4, 1998 Selected Papers (Lecture Notes in Computer Science, 1589)

The European Conference Situationin The General Area Of Software Science Has Longbeen Considered Unsatisfactory. A Fairlylarge Number Of Small And Medi- Sized Conferences And Workshops Take Place On An Irregular Basis, Competing For High-quality Contributions And For Enough Attendees To Make Them ?nancially Viable. Discussions Aiming At A Consolidation Have Been Underway Since At Least 1992, With Concrete Planning Beginning In Summer 1994 And Culminating In A Public Meeting At Tapsoft’95 In Aarhus. On The Basis Of A Broad Consensus, It Was Decided To Establish A Single Annual Federated Spring Conference In The Slot That Was Then Occupied By Tapsoft And Caap/esop/cc, Comprising A Number Of Existing And New Conferences And Covering A Spectrum From Theory To Practice. Etaps’98, The ?rst Instance Of The European Joint Conferences On Theory And Practice Of Software, Is Taking Place This Year In Lisbon. It Comprises ?ve Conferences (fossacs, Fase, Esop, Cc, Tacas), Four Workshops (acos, Visual, Wadt, Cmcs), Seven Invited Lectures, And Nine Tutorials. An Algebraic Framework For Separate Type-checking -- Moving Specification Structures Between Logical Systems -- Normal Forms For Partitions And Relations -- Parameterisation Of Logics -- Semantic Constructions For Hidden Algebra -- Functorial Semantics For Multi-algebras -- An Algebra Of Graph Derivations Using Finite (co—) Limit Double Theories -- Hierarchical Heterogeneous Specifications -- Parallel Admissible Graph Rewriting -- Refinements And Modules For Typed Graph Transformation Systems -- Complete Strategies For Term Graph Narrowing -- Non-deterministic Computations In Elan -- Rasiowa-sikorski Deduction Systems: A Handy Tool For Computer Science Logics -- Translating Obj3 Into Casl: The Institution Level -- Casl: A Guided Tour Of Its Design -- Abstract Petri Nets As A Uniform Approach To High-level Petri Nets -- Using Reflection To Specify Transaction Sequences In Rewriting Logic -- Concurrency And Data Types: A Specification Method An Example With Lotos -- The Situation And State Calculus Versus Branching Temporal Logic -- Modular Specification Of Concurrent Systems With Observational Logic -- Proof Normalization Of Structured Algebraic Specifications Is Convergent. José Luiz Fiadeiro (ed.). Includes Bibliographical References. Cover Title page Copyright page Foreword Preface Table of Contents An Algebraic Framework for Separate Type-Checking? Introduction 1 Two Motivating Examples 2 Abstract Type Systems and Logic of Constraints 3 Modeling Generic Modules in an Arbitrary Type System 4 Fixing a Logic of Constraints 5 Conclusion and Related Work References Moving Specification Structures Between Logical Systems ? 1 Introduction 2 Institutions 3 Institution representations 4 Specifications 5 Mod[SP] vs. Mod[^ˆ(SP)] 6 Reusing proof systems 7 Examples 8 Conclusions Normal Forms for Partitions and Relations? 1 Introduction 2 A Categorical View for Di erent Formalisms 3 The General Model: -Spaces 4 A Uni ed View for Nets, Relations and Partitions 5 Conclusion Parameterisation of Logics? 1 Introduction 2 Logic universes 3 Parameterisation 4 Transference theorems 5 Concluding remarks References Semantic Constructions for Hidden Algebra 1 Introduction 2 Preliminaries 3 Semantics with Final/Cofree Families 4 Semantics with Multi-limits 5 Complex Objects in Hidden Algebra 6 Conclusions and Future Work References Functorial Semantics for Multi-algebras? 1 Introduction 2 A short recap on multi-algebras 3 Why algebraic theories do not work for multi-algebras 4 GS-monoidal theories 5 On the structure of theories 6 Partial algebras and multi-algebras, functorially 7 Conclusions References An Algebra of Graph Derivations Using Finite (co{) Limit Double Theories 1 Introduction 2 The Method: Structured Transition Systems 3 The Domain: DPO{Graph Rewriting 4 The Application of the STS{Method to DPO{Graph Rewriting 5 The Algebra of Graph Derivations 6 Conclusion References Hierarchical Heterogeneous Specications Introduction 1 Homogeneous Logics 2 An Example of HSS: A Travel Agency 3 HHS Theory 4 Heterogeneous Structured Proofs 5 Conclusion References Parallel Admissible Graph Rewriting 1 Introduction 2 De nitions and notations 3 Admissible graph rewriting 4 Parallel admissible graph rewriting 5 Conclusion References Refinements and Modules for Typed Graph Transformation Systems ? 1 Introduction 2 Preliminaries 3 Refinements 4 Modules for Typed Graph Transformation Systems 5 Towards an Algebra of Modules 6 Conclusions References Complete Strategies for Term Graph Narrowing? 1 Introduction 2 Term Graphs and Substitutions 3 Term Graph Narrowing 4 The Lifting Lemma 5 Basic Term Graph Narrowing 6 Minimally Collapsing Narrowing 7 Maximally Collapsing Narrowing 8 Conclusion References Non-deterministic Computations in ELAN 1 Introduction 2 Programs and evaluation mechanism of ELAN 3 Non-determinism in ELAN 4 Determinism analysis 5 Conclusion References Rasiowa-Sikorski Deduction Systems: A Handy Tool for Computer Science Logics 1 Introduction 2 Presentation of the formalism 3 Signed formulae 4 Three-valued logics 5 Similarity logic 6 A logic for nondeterministic specications 7 Many-sorted first order logic with possibly emptycarriers of some sorts 8 Conclusions References Translating OBJ3 into CASL: The Institution Level 1 Introduction 2 Preliminaries 3 The institutions underlying OBJ3 4 Translating the OBJ3 institutions to the CASL institution 5 Translating OBJ3 constructs into CASL constructs 6 Conclusion References CASL: A Guided Tour of Its Design 1 Background 2 Guide 3 Basic Specifications 4 Structured Specifications 5 Architectural Specifications 6 Libraries of Specifications 7 Foreground References Abstract Petri Nets as a Uniform Approach to High-Level Petri Nets 1 Introduction 2 The Data Type Part for Abstract Petri Nets 3 Abstract Petri Nets 4 Results for Abstract Petri Nets 5 Conclusion References Using Reflection to Specify Transaction Sequences in Rewriting Logic 1 Introduction 2 Rewriting Logic and Reflection 3 The Internal Strategy Language 4 A Network Application 5 Strategies and Rules for the Modification Process 6 Comparison of the Two Approaches 7 Improving Control by Changing Strategies 8 Concluding Remarks References Concurrency and Data Types: A Specification Method An Example with LOTOS 1 Introduction 2 A Short Presentation of LOTOS 3 Existing Methods for LOTOS Specification 4 A New Method for LOTOS Specification 5 Conclusion References The Situation and State Calculus versus Branching Temporal Logic ? 1 Introduction 2 The situation and state calculus 3 SSC versus BTL 4 Concluding remarks References A Logical structures Modular Specication of Concurrent Systems with Observational Logic? 1 Introduction 2 Systems, finite observations and quantales 3 Observational logic 4 Example: Stacks 5 Vertical modularity 6 Horizontal modularity 7 Example: Stack implementations 8 Concluding remarks References Proof Normalization of Structured Algebraic Specifications Is Convergent 1. Introduction 2. Structured algebraic specifications 3. A natural deduction calculus 4. Proof term reductions 5. Strong normalization 6. Concluding remarks Author Index This book constitutes the thoroughly refereed post-workshop proceedings of the 13th International Workshop on Algebraic Development Techniques, WADT'98, held in Lisbon, Portugal, in April 1998, as part of ETAPS'98. The 21 revised full papers presented were selected during two rounds of reviewing and revision for inclusion in the book. The papers address all current issues in the area, in particular algebraic (and other) specification techniques, algebraic combination of logics, algebraic structures and logics for concurrency, other algebraic structures and their logics, specification languages and their associated methods and tools, and term rewriting and theorem proving