Computer Science Logic: 23rd International Workshop, CSL 2009, 18th Annual Conference of the EACSL, Coimbra, Portugal, September 7-11, 2009, Proceedings (Lecture Notes in Computer Science (5771))

The annual conference of the European Association for Computer Science Logic (EACSL), CSL 2009, was held in Coimbra (Portugal), September 7–11, 2009. The conference series started as a programme of International Workshops on Computer Science Logic, and then at its sixth meeting became the Annual C- ference of the EACSL. This conference was the 23rd meeting and 18th EACSL conference; it was organized at the Department of Mathematics, Faculty of S- ence and Technology, University of Coimbra. In response to the call for papers, a total of 122 abstracts were submitted to CSL 2009of which 89 werefollowedby a full paper. The ProgrammeCommittee selected 34 papers for presentation at the conference and publication in these proceedings. The Ackermann Award is the EACSL Outstanding Dissertation Award for Logic in Computer Science. The awardrecipient for 2009 was Jakob Nordstr ̈ om. Citation of the award, abstract of the thesis, and a biographical sketch of the recipient may be found at the end of the proceedings. The award was sponsored for the years 2007–2009 by Logitech S.A. Front Matter....Pages - Algebra for Tree Languages....Pages 1-1 Forcing and Type Theory....Pages 2-2 Functional Interpretations of Intuitionistic Linear Logic....Pages 3-19 Fixed-Point Definability and Polynomial Time....Pages 20-23 Kleene’s Amazing Second Recursion Theorem....Pages 24-39 Typed Applicative Structures and Normalization by Evaluation for System F ω ....Pages 40-54 Jumping Boxes....Pages 55-70 Tree-Width for First Order Formulae....Pages 71-85 Algorithmic Analysis of Array-Accessing Programs....Pages 86-101 Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems....Pages 102-116 Cardinality Quantifiers in MLO over Trees....Pages 117-131 From Coinductive Proofs to Exact Real Arithmetic....Pages 132-146 On the Relation between Sized-Types Based Termination and Semantic Labelling....Pages 147-162 Expanding the Realm of Systematic Proof Theory....Pages 163-178 EXPTIME Tableaux for the Coalgebraic μ -Calculus....Pages 179-193 On the Word Problem for ${\it \Sigma\Pi}$ -Categories, and the Properties of Two-Way Communication....Pages 194-208 Intersection, Universally Quantified, and Reference Types....Pages 209-224 Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata....Pages 225-239 Enriching an Effect Calculus with Linear Types....Pages 240-254 Degrees of Undecidability in Term Rewriting....Pages 255-270 Upper Bounds on Stream I/O Using Semantic Interpretations....Pages 271-286 Craig Interpolation for Linear Temporal Languages....Pages 287-301 On Model Checking Boolean BI....Pages 302-316 Efficient Type-Checking for Amortised Heap-Space Analysis....Pages 317-331 Deciding the Inductive Validity of ∀ ∃ * Queries....Pages 332-347 On the Parameterised Intractability of Monadic Second-Order Logic....Pages 348-363 Automatic Structures of Bounded Degree Revisited....Pages 364-378 Nondeterminism and Observable Sequentiality....Pages 379-393 A Decidable Spatial Logic with Cone-Shaped Cardinal Directions....Pages 394-408 Focalisation and Classical Realisability....Pages 409-423 Decidable Extensions of Church’s Problem....Pages 424-439 Nested Hoare Triples and Frame Rules for Higher-Order Store....Pages 440-454 A Complete Characterization of Observational Equivalence in Polymorphic λ -Calculus with General References....Pages 455-469 Non-Commutative First-Order Sequent Calculus....Pages 470-484 Model Checking FO (R) over One-Counter Processes and beyond....Pages 485-499 Confluence of Pure Differential Nets with Promotion....Pages 500-514 Decision Problems for Nash Equilibria in Stochastic Games....Pages 515-529 On the Complexity of Branching-Time Logics....Pages 530-545 Nominal Domain Theory for Concurrency....Pages 546-560 The Ackermann Award 2009....Pages 561-565 Back Matter....Pages - This book constitutes the proceedings of the 23rd International Workshop on Computer Science Logic, CSL 2009, held in Coimbra, Portugal, in September 2009. The 34 papers presented together with 5 invited talks were carefully reviewed and selected from 89 full paper 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, the EACSL Outstanding Dissertation Award for Logic in Computer Science