Computer Science Logic

The 1999 Annual Conference of the European Association for Computer Science Logic, CSL'99, was held in Madrid, Spain, on September 20-25, 1999. CSL'99 was the 13th in a series of annual meetings, originally intended as Internat- nal Workshops on Computer Science Logic, and the 8th to be held as the - nual Conference of the EACSL. The conference was organized by the Computer Science Departments (DSIP and DACYA) at Universidad Complutense in M- rid (UCM). The CSL'99 program committee selected 34 of 91 submitted papers for p- sentation at the conference and publication in this proceedings volume. Each submitted paper was refereed by at least two, and in almost all cases, three di erent referees. The second refereeing round, previously required before a - per was accepted for publication in the proceedings, was dropped following a decision taken by the EACSL membership meeting held during CSL'98 (Brno, Czech Republic, August 25, 1998).

Inhalt

Invited Papers.- Topological Queries in Spatial Databases.- The Consistency Dimension, Compactness, and Query Learning.- Descriptive and Parameterized Complexity.- Logical Specification of Operational Semantics.- Constraint-Based Analysis of Broadcast Protocols.- Contributed Papers.- Descriptive Complexity Theory for Constraint Databases.- Applicative Control and Computational Complexity.- Applying Rewriting Techniques to the Verification of Erlang Processes.- Difference Decision Diagrams.- Analysis of Hybrid Systems: An Ounce of Realism Can Save an Infinity of States.- Verifying Liveness by Augmented Abstraction.- Signed Interval Logic.- Quantitative Temporal Logic.- An Expressively Complete Temporal Logic without Past Tense Operators for Mazurkiewicz Traces.- Using Fields and Explicit Substitutions to Implement Objects and Functions in a de Bruijn Setting.- Closed Reductions in the ?-Calculus.- Kripke Resource Models of a Dependently-Typed, Bunched ?-Calculus (Extended Abstract).- A Linear Logical View of Linear Type Isomorphisms.- Choice Logic Programs and Nash Equilibria in Strategic Games.- Resolution Method for Modal Logic with Well-Founded Frames.- A NExpTime-Complete Description Logic Strictly Contained in C 2.- A Road-Map on Complexity for Hybrid Logics.- MonadicNLIN and Quantifier-Free Reductions.- Directed Reachability: From Ajtai-Fagin to Ehrenfeucht-Fraïssé Games.- Fixpoint Alternation and the Game Quantifier.- Lower Bounds for Space in Resolution.- Program Schemes, Arrays, Lindström Quantifiers and Zero-One Laws.- Open Least Element Principle and Bounded Query Computation.- A Universal Innocent Game Model for the Böhm Tree Lambda Theory.- Anti-Symmetry of Higher-Order Subtyping.- Safe Proof Checking in Type Theory with Y.- Monadic Presentations of Lambda Terms Using Generalized Inductive Types.- A P-Time Completeness Proof for Light Logics.- On Guarding Nested Fixpoints.- A Logical Viewpoint on Process-Algebraic Quotients.- A Truly Concurrent Semantics for a Simple Parallel Programming Language.- Specification Refinement with System F.- Pre-logical Relations.- Data-Refinement for Call-By-Value Programming Languages.- Tutorials.- Tutorial on Term Rewriting.- Tutorial on Interactive Theorem Proving Using Type Theory.