Foundations of software science and computation structures : 7th international conference, FOSSACS 2004, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004, Barcelona, Spain, March 29 - April 2, 2004 : proceeding

Etaps 2004 Was The Seventh Instance Of The European Joint Conferences On Theory And Practice Of Software. Etaps Is An Annual Federated Conference That Was Established In 1998 By Combining A Number Of Existing And New Conferences. This Year It Comprised ?ve Conferences (fossacs, Fase, Esop, Cc, Tacas), 23 Satellite Workshops, 1 Tutorial, And 7 Invited Lectures (not Including Those That Are Speci?c To The Satellite Events). The Events That Comprise Etaps Address Various Aspects Of The System - Velopment Process, Including Speci?cation, Design, Implementation, Analysis And Improvement. The Languages, Methodologies And Tools That Support These - Tivities Are All Well Within Its Scope. Di?erent Blends Of Theory And Practice Are Represented, With An Inclination Towards Theory With A Practical Motivation On The One Hand And Soundly Based Practice On The Other. Many Of The Issues Inv- Ved In Software Design Apply To Systems In General, Including Hardware Systems, And The Emphasis On Software Is Not Intended To Be Exclusive. Invited Contributions -- Intruder Theories (ongoing Work) -- Theories For The Global Ubiquitous Computer -- Contributed Papers -- Choice In Dynamic Linking -- Soft Lambda-calculus: A Language For Polynomial Time Computation -- On The Existence Of An Effective And Complete Inference System For Cryptographic Protocols -- Hypergraphs And Degrees Of Parallelism: A Completeness Result -- Behavioral And Spatial Observations In A Logic For The ?-calculus -- Election And Local Computations On Edges -- Decidability Of Freshness, Undecidability Of Revelation -- Ltl Over Integer Periodicity Constraints -- Unifying Recursive And Co-recursive Definitions In Sheaf Categories -- Deriving Bisimulation Congruences In The Dpo Approach To Graph Rewriting -- A Denotational Account Of Untyped Normalization By Evaluation -- On Finite Alphabets And Infinite Bases: From Ready Pairs To Possible Worlds -- Specifying And Verifying Partial Order Properties Using Template Mscs --^ Angelic Semantics Of Fine-grained Concurrency -- On The Expressiveness Of Infinite Behavior And Name Scoping In Process Calculi -- Safedpi: A Language For Controlling Mobile Code -- Distance Desert Automata And The Star Height One Problem -- Adhesive Categories -- A Game Semantics Of Local Names And Good Variables -- Partial Correctness Assertions Provable In Dynamic Logics -- Polynomials For Proving Termination Of Context-sensitive Rewriting -- Bisimulation On Speed: Lower Time Bounds -- On Recognizable Timed Languages -- Tree Transducers And Tree Compressions -- On Term Rewriting Systems Having A Rational Derivation -- Duality For Labelled Markov Processes -- Electoral Systems In Ambient Calculi -- Strong Normalization Of -calculus With Explicit Substitutions -- Canonical Models For Computational Effects -- Reasoning About Dynamic Policies -- Probabilistic Bisimulation And Equivalence For Security Analysis Of Network Protocols --^ Strong Bisimulation For The Explicit Fusion Calculus -- Perfect-information Stochastic Parity Games -- A Note On The Perfect Encryption Assumption In A Process Calculus. Igor Walukiewicz (ed.). Includes Bibliographical References And Index. Front Matter....Pages - Intruder Theories (Ongoing Work)....Pages 1-4 Theories for the Global Ubiquitous Computer....Pages 5-11 Choice in Dynamic Linking....Pages 12-26 Soft lambda-Calculus: A Language for Polynomial Time Computation....Pages 27-41 On the Existence of an Effective and Complete Inference System for Cryptographic Protocols....Pages 42-57 Hypergraphs and Degrees of Parallelism: A Completeness Result....Pages 58-71 Behavioral and Spatial Observations in a Logic for the π -Calculus....Pages 72-89 Election and Local Computations on Edges....Pages 90-104 Decidability of Freshness, Undecidability of Revelation....Pages 105-120 LTL over Integer Periodicity Constraints....Pages 121-135 Unifying Recursive and Co-recursive Definitions in Sheaf Categories....Pages 136-150 Deriving Bisimulation Congruences in the DPO Approach to Graph Rewriting....Pages 151-166 A Denotational Account of Untyped Normalization by Evaluation....Pages 167-181 On Finite Alphabets and Infinite Bases: From Ready Pairs to Possible Worlds....Pages 182-194 Specifying and Verifying Partial Order Properties Using Template MSCs....Pages 195-210 Angelic Semantics of Fine-Grained Concurrency....Pages 211-225 On the Expressiveness of Infinite Behavior and Name Scoping in Process Calculi....Pages 226-240 safeDpi : A Language for Controlling Mobile Code....Pages 241-256 Distance Desert Automata and the Star Height One Problem....Pages 257-272 Adhesive Categories....Pages 273-288 A Game Semantics of Local Names and Good Variables....Pages 289-303 Partial Correctness Assertions Provable in Dynamic Logics....Pages 304-317 Polynomials for Proving Termination of Context-Sensitive Rewriting....Pages 318-332 Bisimulation on Speed: Lower Time Bounds....Pages 333-347 On Recognizable Timed Languages....Pages 348-362 Tree Transducers and Tree Compressions....Pages 363-377 On Term Rewriting Systems Having a Rational Derivation....Pages 378-392 Duality for Labelled Markov Processes....Pages 393-407 Electoral Systems in Ambient Calculi....Pages 408-422 Strong Normalization of $\overline{\lambda}\mu\widetilde{\mu}$ -Calculus with Explicit Substitutions....Pages 423-437 Canonical Models for Computational Effects....Pages 438-452 Reasoning about Dynamic Policies....Pages 453-467 Probabilistic Bisimulation and Equivalence for Security Analysis of Network Protocols....Pages 468-483 Strong Bisimulation for the Explicit Fusion Calculus....Pages 484-498 Perfect-Information Stochastic Parity Games....Pages 499-513 A Note on the Perfect Encryption Assumption in a Process Calculus....Pages 514-528 Back Matter....Pages - Foundations of Software Science and Computation Structures: 7th International Conference, FOSSACS 2004, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004, Barcelona, Spain, March 29 – April 2, 2004. Proceedings Author: Igor Walukiewicz Published by Springer Berlin Heidelberg ISBN: 978-3-540-21298-0 DOI: 10.1007/b95995 Table of Contents: Intruder Theories (Ongoing Work) Theories for the Global Ubiquitous Computer Choice in Dynamic Linking Soft lambda-Calculus: A Language for Polynomial Time Computation On the Existence of an Effective and Complete Inference System for Cryptographic Protocols Hypergraphs and Degrees of Parallelism: A Completeness Result Behavioral and Spatial Observations in a Logic for the π-Calculus Election and Local Computations on Edges Decidability of Freshness, Undecidability of Revelation LTL over Integer Periodicity Constraints Unifying Recursive and Co-recursive Definitions in Sheaf Categories Deriving Bisimulation Congruences in the DPO Approach to Graph Rewriting A Denotational Account of Untyped Normalization by Evaluation On Finite Alphabets and Infinite Bases: From Ready Pairs to Possible Worlds Specifying and Verifying Partial Order Properties Using Template MSCs Angelic Semantics of Fine-Grained Concurrency On the Expressiveness of Infinite Behavior and Name Scoping in Process Calculi safeDpi: A Language for Controlling Mobile Code Distance Desert Automata and the Star Height One Problem Adhesive Categories This book constitutes the refereed proceedings of the 7th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2004, held in Barcelona, Spain in March/April 2004. The 34 revised full papers presented together with the abstracts of 2 invited talks were carefully reviewed and selected from over 130 submissions. Among the topics addressed are lambda calculus, cryptographic protocol analysis, graphs and grammar systems, decision theory, bisimulation, rewriting, normalization, specification, verification, process calculi, mobile code, automata, program semantics, dynamic logics, timed languages, security analysis, information-theoretical aspects