Foundations of Software Science and Computational Structures: 11th International Conference, Fossacs 2008, Held as Part of the Joint European Conferen

ISBN-13: 9783540784975 / Angielski / Miękka / 2008 / 508 str.

Amadio, Roberto

Opis

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.

Spis treści

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 Stochastic Process 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.