Foundations of Software Science and Computation Structures

1. Front Matter

   PDF

2. Equivalences of Pushdown Systems Are Hard

   • Petr Jančar

   Pages 1-28

3. Probabilistic Systems

   1. Active Diagnosis for Probabilistic Systems

      • Nathalie Bertrand, Éric Fabre, Stefan Haar, Serge Haddad, Loïc Hélouët

      Pages 29-42

   2. Analysis of Probabilistic Basic Parallel Processes

      • Rémi Bonnet, Stefan Kiefer, Anthony Widjaja Lin

      Pages 43-57

   3. Limit Synchronization in Markov Decision Processes

      • Laurent Doyen, Thierry Massart, Mahsa Shirmohammadi

      Pages 58-72

   4. Maximal Cost-Bounded Reachability Probability on Continuous-Time Markov Decision Processes

      • Hongfei Fu

      Pages 73-87

4. Semantics of Programming Languages

   1. Type Reconstruction for the Linear π-Calculus with Composite and Equi-Recursive Types

      • Luca Padovani

      Pages 88-102

   2. A Semantical and Operational Account of Call-by-Value Solvability

      • Alberto Carraro, Giulio Guerrieri

      Pages 103-118

5. Networks

   1. Network-Formation Games with Regular Objectives

      • Guy Avni, Orna Kupferman, Tami Tamir

      Pages 119-133

   2. Playing with Probabilities in Reconfigurable Broadcast Networks

      • Nathalie Bertrand, Paulin Fournier, Arnaud Sangnier

      Pages 134-148

6. Program Analysis

   1. Unsafe Order-2 Tree Languages Are Context-Sensitive

      • Naoki Kobayashi, Kazuhiro Inaba, Takeshi Tsukada

      Pages 149-163

   2. Game Semantics for Nominal Exceptions

      • Andrzej S. Murawski, Nikos Tzevelekos

      Pages 164-179

   3. Complexity of Model-Checking Call-by-Value Programs

      • Takeshi Tsukada, Naoki Kobayashi

      Pages 180-194

7. Games and Synthesis

   1. Resource Reachability Games on Pushdown Graphs

      • Martin Lang

      Pages 195-209

   2. Perfect-Information Stochastic Mean-Payoff Parity Games

      • Krishnendu Chatterjee, Laurent Doyen, Hugo Gimbert, Youssouf Oualhadj

      Pages 210-225

   3. Latticed-LTL Synthesis in the Presence of Noisy Inputs

      • Shaull Almagor, Orna Kupferman

      Pages 226-241

   4. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies

      • Krishnendu Chatterjee, Laurent Doyen, Sumit Nain, Moshe Y. Vardi

      Pages 242-257

8. Compositional Reasoning

   1. On Negotiation as Concurrency Primitive II: Deterministic Cyclic Negotiations

      • Javier Esparza, Jörg Desel

      Pages 258-273

   2. On Asymmetric Unification and the Combination Problem in Disjoint Theories

      • Serdar Erbatur, Deepak Kapur, Andrew M. Marshall, Catherine Meadows, Paliath Narendran, Christophe Ringeissen

      Pages 274-288

9. Bisimulation

   1. Axiomatizing Bisimulation Equivalences and Metrics from Probabilistic SOS Rules

      • Pedro R. D’Argenio, Daniel Gebler, Matias David Lee

      Pages 289-303

This book constitutes the proceedings of the 17th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2014, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, which took place in Grenoble, France, in April 2014. The 28 papers included in this book, together with one invited talk, were selected from 106 full-paper submissions. The following topical areas are covered: probabilistic systems, semantics of programming languages, networks, program analysis, games and synthesis, compositional reasoning, bisimulation, categorical and algebraic models and logics of programming.

• Markov decision processes
• algebraic semantics
• bisimulation
• categorical semantics
• formal methods
• game theory
• logics of programming
• networks
• probabilistic systems
• probability and statistics
• program analysis
• program semantics
• program verification
• semantics and reasoning
• software analysis
• software engineering
• software systems
• software verification
• theory of computation

• LaBRI, Universiy of Bordeaux, France

  Anca Muscholl

Policies and ethics