Foundations of Software Science and Computation Structures

1. Front Matter

   Pages I-XVII

   PDF

2. Coherence Spaces and Higher-Order Computation

   1. Front Matter

      Pages 1-1

      PDF

   2. Coherence Spaces and Uniform Continuity

      • Kei Matsumoto

      Pages 3-19

   3. The Free Exponential Modality of Probabilistic Coherence Spaces

      • Raphaëlle Crubillé, Thomas Ehrhard, Michele Pagani, Christine Tasson

      Pages 20-35

   4. From Qualitative to Quantitative Semantics

      • James Laird

      Pages 36-52

   5. Almost Every Simply Typed \(\lambda \)-Term Has a Long \(\beta \)-Reduction Sequence

      • Ryoma Sin’ya, Kazuyuki Asada, Naoki Kobayashi, Takeshi Tsukada

      Pages 53-68

3. Algebra and Coalgebra

   1. Front Matter

      Pages 69-69

      PDF

   2. Algebra, Coalgebra, and Minimization in Polynomial Differential Equations

      • Michele Boreale

      Pages 71-87

   3. Equational Theories of Abnormal Termination Based on Kleene Algebra

      • Konstantinos Mamouras

      Pages 88-105

   4. Companions, Codensity and Causality

      • Damien Pous, Jurriaan Rot

      Pages 106-123

   5. Nominal Automata with Name Binding

      • Lutz Schröder, Dexter Kozen, Stefan Milius, Thorsten Wißmann

      Pages 124-142

4. Games and Automata

   1. Front Matter

      Pages 143-143

      PDF

   2. On the Existence of Weak Subgame Perfect Equilibria

      • Véronique Bruyère, Stéphane Le Roux, Arno Pauly, Jean-François Raskin

      Pages 145-161

   3. Optimal Reachability in Divergent Weighted Timed Games

      • Damien Busatto-Gaston, Benjamin Monmege, Pierre-Alain Reynier

      Pages 162-178

   4. Bounding Average-Energy Games

      • Patricia Bouyer, Piotr Hofman, Nicolas Markey, Mickael Randour, Martin Zimmermann

      Pages 179-195

   5. Logics of Repeating Values on Data Trees and Branching Counter Systems

      • Sergio Abriola, Diego Figueira, Santiago Figueira

      Pages 196-212

5. Automata, Logic and Formal Languages

   1. Front Matter

      Pages 213-213

      PDF

   2. Degree of Sequentiality of Weighted Automata

      • Laure Daviaud, Ismaël Jecker, Pierre-Alain Reynier, Didier Villevalois

      Pages 215-230

   3. Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata

      • Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

      Pages 231-247

   4. Partial Derivatives for Context-Free Languages

      • Peter Thiemann

      Pages 248-264

This book constitutes the proceedings of the 20th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2017, which took place in Uppsala, Sweden in April 2017, held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017.

The 32 papers presented in this volume were carefully reviewed and selected from 101 submissions. They were organized in topical sections named: coherence spaces and higher-order computation; algebra and coalgebra; games and automata; automata, logic and formal languages; proof theory; probability; concurrency; lambda calculus and constructive proof; and semantics and category theory.

• software engineering
• formal logic
• mathematical logic
• formal languages
• programming languages
• compilers
• interpreters
• finite automata
• coalgebra
• numerical methods
• Markov chains
• probability
• semantics
• satisfiability problems
• artificial intelligence
• context free languages

• TU München, Garching, Germany

  Javier Esparza

• University of Warwick, Coventry, United Kingdom

  Andrzej S. Murawski

Policies and ethics