Foundations of Software Science and Computational Structures

This book contains the proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures. It covers theories and methods to support analysis, synthesis, transformation and verification of software systems.

ETAPS2008wasthe11thinstanceoftheEuropeanJointConferencesonTheory 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 yearit comprised?ve conferences (CC, ESOP,FASE, FOSSACS, TACAS), 22satelliteworkshops(ACCAT,AVIS,Bytecode,CMCS,COCV,DCC,FESCA, FIT, FORMED, GaLoP, GT-VMT, LDTA, MBT, MOMPES, PDMC, QAPL, RV,SafeCert,SC,SLA++P,WGT,andWRLA),ninetutorials,andseveninvited lectures (excluding those that were speci?c to the satellite events). The ?ve main conferences received 571 submissions, 147 of which were accepted, giving an overall acceptance rate of less than 26%, with each conference below 27%. Congratulationsthereforetoallthe authorswhomadeittothe ?nalprogramme! I hope that most of the other authors will still have found a way of participating in this exciting event, and that you will all continue submitting to ETAPS and contributing to make of it the best conference in the area. 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 which 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 involved in software design apply to systems in general, including hardware s- tems, and the emphasis on software is not intended to be exclusive.

Klappentext
This book constitutes the refereed proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2008, held in Budapest, Hungary, in March/April 2008 as part of ETAPS 2008, the European Joint Conferences on Theory and Practice of Software. The 33 revised full papers presented together with the abstract of 1 invited talk were carefully reviewed and selected from 124 submissions. A broad variety of theories and methods to support analysis, synthesis, transformation and verification of programs and software systems are addressed, including the following topics: algebraic models, automata and language theory, behavioural equivalences, categorical models, computation processes over discrete and continuous data, infinite state systems, computational structures, logics of programs, modal, spatial, and temporal logics, models of concurrent, reactive, distributed, and mobile systems, process algebras and calculi, semantics of programming languages, software specification and refinement, type systems and type theory, fundamentals of security, semi-structured data, program correctness and verification.

Inhalt
Finding Your Way in a Forest: On Different Types of Trees and Their Properties.- Simple Stochastic Games with Few Random Vertices Are Easy to Solve.- The Complexity of Nash Equilibria in Infinite Multiplayer Games.- Stochastic Games with Lossy Channels.- Simulation Hemi-metrics between Infinite-State Stochastic Games.- Beyond Rank 1: Algebraic Semantics and Finite Models for Coalgebraic Logics.- A Linear-non-Linear Model for a Computational Call-by-Value Lambda Calculus (Extended Abstract).- The ?-Regular Post Embedding Problem.- Complexity of Decision Problems for Mixed and Modal Specifications.- Classes of Tree Homomorphisms with Decidable Preservation of Regularity.- A Kleene-Schützenberger Theorem for Weighted Timed Automata.- Robust Analysis of Timed Automata Via Channel Machines.- The Common Fragment of ACTL and LTL.- The Complexity of CTL* + Linear Past.- Footprints in Local Reasoning.- A Modal Deconstruction of Access Control Logics.- Coalgebraic Logic and Synthesis of Mealy Machines.- The Microcosm Principle and Concurrency in Coalgebra.- Systems of Equations Satisfied in All Commutative Finite Semigroups.- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.- On Decision Problems for Probabilistic Büchi Automata.- Model-Checking ?-Regular Properties of Interval Markov Chains.- Prevision Domains and Convex Powercones.- RPO, Second-Order Contexts, and ?-Calculus.- Erasure and Polymorphism in Pure Type Systems.- The Implicit Calculus of Constructions as a Programming Language with Dependent Types.- Strong Normalisation of Cut-Elimination That Simulates ?-Reduction.- Symbolic Semantics Revisited.- Deriving Bisimulation Congruences in the Presence of Negative Application Conditions.- Structural Operational Semantics for StochasticProcess Calculi.- Compositional Methods for Information-Hiding.- Products of Message Sequence Charts.- What Else Is Decidable about Integer Arrays?.- Model Checking Freeze LTL over One-Counter Automata.