Computer Science Logic

1. Front Matter

   PDF

2. Invited Talks

   1. The Computability Path Ordering: The End of a Quest

      • Frédéric Blanqui, Jean-Pierre Jouannaud, Albert Rubio

      Pages 1-14

   2. The Joy of String Diagrams

      • Pierre-Louis Curien

      Pages 15-22

   3. Model Transformations in Decidability Proofs for Monadic Theories

      • Wolfgang Thomas

      Pages 23-31

   4. Molecules as Automata

      • Luca Cardelli

      Pages 32-32

3. Contributed Papers

   1. An Infinite Automaton Characterization of Double Exponential Time

      • Salvatore La Torre, P. Madhusudan, Gennaro Parlato

      Pages 33-48

   2. Recursion Schemata for NC^k

      • Guillaume Bonfante, Reinhard Kahle, Jean-Yves Marion, Isabel Oitavem

      Pages 49-63

   3. Extensional Uniformity for Boolean Circuits

      • Pierre McKenzie, Michael Thomas, Heribert Vollmer

      Pages 64-78

   4. Pure Pointer Programs with Iteration

      • Martin Hofmann, Ulrich Schöpp

      Pages 79-93

   5. Quantified Positive Temporal Constraints

      • Witold Charatonik, Michał Wrona

      Pages 94-108

   6. Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint

      • Nadia Creignou, Henning Schnoor, Ilka Schnoor

      Pages 109-123

   7. Fractional Collections with Cardinality Bounds, and Mixed Linear Arithmetic with Stars

      • Ruzica Piskac, Viktor Kuncak

      Pages 124-138

   8. Continuous Fragment of the mu-Calculus

      • Gaëlle Fontaine

      Pages 139-153

   9. On the Relations between the Syntactic Theories of λμ-Calculi

      • Alexis Saurin

      Pages 154-168

   10. A Constructive Semantic Approach to Cut Elimination in Type Theories with Axioms

       • Olivier Hermant, James Lipton

       Pages 169-183

   11. Proving Infinitude of Prime Numbers Using Binomial Coefficients

       • Phuong Nguyen

       Pages 184-198

   12. A Tight Karp-Lipton Collapse Result in Bounded Arithmetic

       • Olaf Beyersdorff, Sebastian Müller

       Pages 199-214

   13. A Calculus of Realizers for EM ₁ Arithmetic (Extended Abstract)

       • Stefano Berardi, Ugo de’Liguoro

       Pages 215-229

   14. Quantitative Game Semantics for Linear Logic

       • Ugo Dal Lago, Olivier Laurent

       Pages 230-245

   15. A Characterization of Hypercoherent Semantic Correctness in Multiplicative Additive Linear Logic

       • Paolo Tranquilli

       Pages 246-261

This book constitutes the refereed proceedings of the 22nd International Workshop on Computer Science Logic, CSL 2008, held as the 17th Annual Conference of the EACSL in Bertinoro, Italy, in September 2008. The 31 revised full papers presented together with 4 invited lectures were carefully reviewed and selected from 102 submissions. All current aspects of logic in computer science are addressed, ranging from foundational and methodological issues to application issues of practical relevance. The book concludes with a presentation of this year's Ackermann award.

• Arithmetic
• C programming language
• Finite
• Joy
• Morphism
• algorithms
• calculi
• classical logic
• complexity
• higher order logic
• logic programming
• mathematical logic
• model checking
• optimization
• proving

Policies and ethics