Computer Science Logic

This book constitutes the refereed proceedings of the 15th International Workshop on Computer Science Logic, CSL 2001, held as the 10th Annual Conerence of the EACSL in Paris, France in September 2001.The 39 revised full papers presented together with two invited papers were carefully reviewed and selected from 91 submissions. The papers are organized in topical sections on linear logic, descriptive complexity, semantics, higher-order programs, model logics, verification, automata, lambda calculus, induction, equational calculus, and constructive theory of types.

Inhalt

Invited Papers.- Local Reasoning about Programs that Alter Data Structures.- Applications of Alfred Tarski's Ideas in Database Theory.- Locus Solum: From the Rules of Logic to the Logic of Rules.- Contributed Papers.- The Expressive Power of Horn Monadic Linear Logic.- Non-commutativity and MELL in the Calculus of Structures.- Quadratic Correctness Criterion for Non-commutative Logic.- Descriptive Complexity.- Capture Complexity by Partition.- An Existential Locality Theorem.- Actual Arithmetic and Feasibility.- The Natural Order-Generic Collapse for ?-Representable Databases over the Rational and the Real Ordered Group.- Semantics.- An Algebraic Foundation for Higraphs.- Semantic Characterisations of Second-Order Computability over the Real Numbers.- An Abstract Look at Realizability.- The Anatomy of Innocence.- Higher-Order Programs.- An Improved Extensionality Criterion for Higher-Order Logic Programs.- A Logic for Abstract State Machines.- Constrained Hyper Tableaux.- Modal Logics.- Modal Logic and the Two-Variable Fragment.- A Logic for Approximate First-Order Reasoning.- Inflationary Fixed Points in Modal Logic.- Categorical and Kripke Semantics for Constructive S4 Modal Logic.- Verification.- Labelled Natural Deduction for Interval Logics.- Decidable Navigation Logics for Object Structures.- The Decidability of Model Checking Mobile Ambients.- Automata.- A Generalization of the Büchi-Elgot-Trakhtenbrot Theorem.- An Effective Extension of the Wagner Hierarchy to Blind Counter Automata.- Decision Procedure for an Extension of WS1S.- Lambda-Calculus.- Limiting Partial Combinatory Algebras towards Infinitary Lambda-Calculi and Classical Logic.- Intersection Logic.- Life without the Terminal Type.- Fully Complete Minimal PER Models for the Simply Typed ?-Calculus.- Induction.- A Principle of Induction.- On a Generalisation of Herbrand's Theorem.- Well-Founded Recursive Relations.- Equational Calculus.- Stratified Context Unification Is in PSPACE.- Uniform Derivation of Decision Procedures by Superposition.- Complete Categorical Equational Deduction.- Beyond Regularity: Equational Tree Automata for Associative and Commutative Theories.- Constructive Theory of Types.- Normalized Types.- Markov's Principle for Propositional Type Theory.- Recursion for Higher-Order Encodings.- Monotone Inductive and Coinductive Constructors of Rank 2.