Foundations of software science and computation structures : Second International Conference, FOSSACS '99 held as part of the joint European Conferences on Theory and Practice of Software, ETAPS '99, Amsterdam, the Netherlands, March 22-28, 1999 : proceed

This book constitutes the refereed proceedings of the Second International Conference on Foundations of Software Science and Computation Structures, FOSSACS '99, held in Amsterdam, The Netherlands in March 1999 as part of ETAPS'99. The 18 revised full papers presented were carefully selected from a total of 40 submissions. Also included are three invited papers. The central issues of the papers are theories and methods which suport the specification, transformation, verification and analysis of programs and software systems. The International Conference “foundations Of Software Science And Compu- Tion Structures” (fossacs) Is A Constituent Of The “joint European Conferences On Theoryand Practice Of Software” (etaps). The Present Volume Contains The Contributions To Fossacs’99, The Second Conference In This Series, Which Took Place In Amsterdam. As Formulated In The Call For Papers, Fossacs Focusses On “papers Which O?er Progress In Foundational Research With A Clear Signi?cance For Software Science. A Central Issue Is Theories And Methods Which Support The Speci?cation, Tra- Formation, Veri?cation, And Analysis Of Programs And Software Systems.” The Articles In This Volume Represent A Wide Spectrum Of Approaches To This General Aim. In Manypapers, One ?nds The Studyof New Concepts And Methods Which Are Motivated Byrecent Trends (or Problems) In The Practical Use Of Software And Information Technology. The Volume Contains 18 Contributed Papers, Preceded Bythree Invited Papers. The ?rst, Bym. Abadi, Accompanies His “unifying Invited Lecture” Addressed To The Whole Etaps Audience. The Second, Byj. Esparza And J. Knoop, Contains An Application Of The Results Presented Byj. Esparza In His Invited Lecture To Fossacs’99. The Third Summarizes An Invited Tutorial Byd. Sangiorgi P- Sented To Etaps’99. Security Protocols And Specifications -- An Automata-theoretic Approach To Interprocedural Data-flow Analysis -- Reasoning About Concurrent Systems Using Types -- Testing Hennessy-milner Logic With Recursion -- A Strong Logic Programming View For Static Embedded Implications -- Unfolding And Event Structure Semantics For Graph Grammars -- Expanding The Cube -- An Algebraic Characterization Of Typability In Ml With Subtyping -- Static Analysis Of Processes For No Read-up And No Write-down -- A Wp-calculus For Oo -- The Recognizability Problem For Tree Automata With Comparisons Between Brothers -- A Theory Of “may” Testing For Asynchronous Languages -- A Nondeterministic Polynomial-time Unification Algorithm For Bags, Sets And Trees -- Categorical Models Of Explicit Substitutions -- Equational Properties Of Mobile Ambients -- Model Checking Logics For Communicating Sequential Agents -- A Complete Coinductive Logical System For Bisimulation Equivalence On Circular Objects -- String Languages Generated By Total Deterministic Macro Tree Transducers -- Matching Specifications For Message Sequence Charts -- Probabilistic Temporal Logics Via The Modal Mu-calculus -- A ?-calculus Process Semantics Of Concurrent Idealised Algol. Wolfgang Thomas, Ed. Includes Bibliographical References And Index. Security Protocols and Specifications....Pages 1-13 An Automata-Theoretic Approach to Interprocedural Data-Flow Analysis....Pages 14-30 Reasoning about Concurrent Systems Using Types....Pages 31-40 Testing Hennessy-Milner Logic with Recursion....Pages 41-55 A Strong Logic Programming View for Static Embedded Implications....Pages 56-72 Unfolding and Event Structure Semantics for Graph Grammars....Pages 73-89 Expanding the Cube....Pages 90-104 An Algebraic Characterization of Typability in ML with Subtyping....Pages 104-119 Static Analysis of Processes for No Read-Up and No Write-Down....Pages 120-134 A WP-calculus for OO....Pages 135-140 The Recognizability Problem for Tree Automata with Comparisons between Brothers....Pages 150-164 A Theory of “May” Testing for Asynchronous Languages....Pages 165-179 A Nondeterministic Polynomial-Time Unification Algorithm for Bags, Sets and Trees....Pages 180-196 Categorical Models of Explicit Substitutions....Pages 197-211 Equational Properties of Mobile Ambients....Pages 212-226 Model Checking Logics for Communicating Sequential Agents....Pages 227-242 A Complete Coinductive Logical System for Bisimulation Equivalence on Circular Objects....Pages 243-257 String Languages Generated by Total Deterministic Macro Tree Transducers....Pages 258-272 Matching Specifications for Message Sequence Charts....Pages 273-287 Probabilistic Temporal Logics via the Modal Mu-Calculus....Pages 288-305 A π-calculus Process Semantics of Concurrent Idealised ALGOL....Pages 306-321 The method of "security by obscurity" dictates that potential attackers to a system should be kept from knowing not only passwords and cryptographic keys but also basic information about how the system works, such as the specifications of cryptographic algorithms, communication protocols, and access-control mechanisms. This volume represents the proceedings of the 2nd International Conference on Foundations of Software Science and Computation Structures. The central issues discussed are theories and methods supporting the specification, transformation, verification and analysis of programs and software systems.