Foundations of software science and computational structures : 10th international conference, FOSSACS 2007, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007, Braga, Portugal, March 24 - April 1, 2007 : proceedi

This book constitutes the refereed proceedings of the 10th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2007, held in Braga, Portugal in March/April 2007 as part of ETAPS 2007, the European Joint Conferences on Theory and Practice of Software. The 25 revised full papers presented together with the abstract of 1 invited talk were carefully reviewed and selected from 103 submissions. The papers cover a broad spectrum on theories and methods to support analysis, synthesis, transformation and verification of programs and software systems. In particular the following topics are dealt with: algebraic models, automata and language theory, behavioral equivalences, categorical models, computation processes over discrete and continuous data, infinite state systems computation 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. Front Matter....Pages - Formal Foundations for Aspects....Pages 1-1 Sampled Universality of Timed Automata....Pages 2-16 Iterator Types....Pages 17-31 Types and Effects for Resource Usage Analysis....Pages 32-47 The Complexity of Generalized Satisfiability for Linear Temporal Logic....Pages 48-62 Formalising the π -Calculus Using Nominal Logic....Pages 63-77 The Rewriting Calculus as a Combinatory Reduction System....Pages 78-92 Relational Parametricity and Separation Logic....Pages 93-107 Model-Checking One-Clock Priced Timed Automata....Pages 108-122 Approximating a Behavioural Pseudometric Without Discount for Probabilistic Systems....Pages 123-137 Optimal Strategy Synthesis in Stochastic Müller Games....Pages 138-152 Generalized Parity Games....Pages 153-167 Tree Automata with Memory, Visibility and Structural Constraints....Pages 168-182 Enriched μ -Calculi Module Checking....Pages 183-197 PDL with Intersection and Converse Is 2 EXP -Complete....Pages 198-212 Symbolic Backwards-Reachability Analysis for Higher-Order Pushdown Systems....Pages 213-227 A Distribution Law for CCS and a New Congruence Result for the π -Calculus....Pages 228-242 On the Expressiveness and Complexity of ATL ....Pages 243-257 Polynomial Constraints for Sets with Cardinality Bounds....Pages 258-273 A Lower Bound on Web Services Composition....Pages 274-286 Logical Characterizations of Bisimulations for Discrete Probabilistic Systems....Pages 287-301 Semantic Barbs and Biorthogonality....Pages 302-316 On the Stability by Union of Reducibility Candidates....Pages 317-331 An Effective Algorithm for the Membership Problem for Extended Regular Expressions....Pages 332-345 Complexity Results on Balanced Context-Free Languages....Pages 346-360 Logical Reasoning for Higher-Order Functions with Local State....Pages 361-377 Back Matter....Pages - Formal Foundations For Aspects / Radha Jagadeesan -- Sampled Universality Of Timed Automata / Parosh Aziz Abdulla, Pavel Krcal And Wang Yi -- Iterator Types / Sandra Alves, Maribel Fernandez, Mario Florida And Ian Mackie -- Types And Effects For Resource Usage Analysis / Massimo Bartoletti, Pierpaolo Degano, Gian Luigi Ferrari And Roberto Zunino -- The Complexity Of Generalized Satisfiability For Linear Temporal Logic / Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor And Heribert Vollmer -- Formalising The [pi]-calculus Using Nominal Logic / Jesper Bengtson And Joachim Parrow -- The Rewriting Calculus As A Combinatory Reduction System / Clara Bertolissi And Claude Kirchner. Helmut Seidl (ed.). International Conference Proceedings. Includes Bibliographical References And Index. This book constitutes the refereed proceedings of the 10th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2007, held in Braga, Portugal in March/April 2007. The 25 revised full papers presented together with the abstract of one invited talk cover a broad spectrum on theories and methods to support analysis, synthesis, transformation and verification of programs and software systems.