Foundations of Software Science and Computational Structures

1. Front Matter

   PDF

2. The Search for Structure in Quantum Computation

   1. The Search for Structure in Quantum Computation

      • Prakash Panangaden

      Pages 1-11

3. Coalgebra and Computability

   1. Coalgebraic Walks, in Quantum and Turing Computation

      • Bart Jacobs

      Pages 12-26

   2. Similarity Quotients as Final Coalgebras

      • Paul Blain Levy

      Pages 27-41

   3. What Do Reversible Programs Compute?

      • Holger Bock Axelsen, Robert Glück

      Pages 42-56

4. Type Theory

   1. Irrelevance in Type Theory with a Heterogeneous Equality Judgement

      • Andreas Abel

      Pages 57-71

   2. When Is a Type Refinement an Inductive Type?

      • Robert Atkey, Patricia Johann, Neil Ghani

      Pages 72-87

   3. Complexity of Strongly Normalising λ-Terms via Non-idempotent Intersection Types

      • Alexis Bernadet, Stéphane Lengrand

      Pages 88-107

   4. Realizability and Parametricity in Pure Type Systems

      • Jean-Philippe Bernardy, Marc Lasson

      Pages 108-122

5. Process Calculi

   1. Sound Bisimulations for Higher-Order Distributed Process Calculus

      • Adrien Piérard, Eijiro Sumii

      Pages 123-137

   2. Deriving Labels and Bisimilarity for Concurrent Constraint Programming

      • Andrés Aristizábal, Filippo Bonchi, Catuscia Palamidessi, Luis Pino, Frank Valencia

      Pages 138-152

   3. Ordinal Theory for Expressiveness of Well Structured Transition Systems

      • Remi Bonnet, Alain Finkel, Serge Haddad, Fernando Rosa-Velardo

      Pages 153-167

6. Automata Theory

   1. Alternation Elimination for Automata over Nested Words

      • Christian Dax, Felix Klaedtke

      Pages 168-183

   2. Co-Büching Them All

      • Udi Boker, Orna Kupferman

      Pages 184-198

   3. Minimizing Deterministic Lattice Automata

      • Shulamit Halamish, Orna Kupferman

      Pages 199-213

   4. Regularity and Context-Freeness over Word Rewriting Systems

      • Didier Caucal, Trong Hieu Dinh

      Pages 214-228

   5. Quantitative Robustness Analysis of Flat Timed Automata

      • Rémi Jaubert, Pierre-Alain Reynier

      Pages 229-244

   6. A Game Approach to Determinize Timed Automata

      • Nathalie Bertrand, Amélie Stainer, Thierry Jéron, Moez Krichen

      Pages 245-259

   7. A Practical Linear Time Algorithm for Trivial Automata Model Checking of Higher-Order Recursion Schemes

      • Naoki Kobayashi

      Pages 260-274

   8. Church Synthesis Problem for Noisy Input

      • Yaron Velner, Alexander Rabinovich

      Pages 275-289

This book constitutes the refereed proceedings of the 14th International Conference on Foundations of Software Science and computational Structures, FOSSACS 2011, held in Saarbrücken, Germany, March 26—April 3, 2011, as part of ETAPS 2011, the European Joint Conferences on Theory and Practice of Software. The 30 revised full papers presented together with one full-paper length invited talk were carefully reviewed and selected from 100 submissions. The papers are organized in topical sections on coalgebra and computability, type theory, process calculi, automata theory, semantics, binding, security, and program analysis.

• abstract machines
• computational complexity
• correctness
• decision procedures
• first order logic
• formal verification
• infinite games
• modal logics
• model checking
• process algebras
• programming languages semantics
• regular games
• security
• software engineering
• theorem proving

• Institut für Informatik, Ludwig-Maximilians-Universität München, München, Germany

  Martin Hofmann

Policies and ethics