| Generating Hard Instances of the Short Basis Problem | p. 1 |
| Wide Area Computation | p. 10 |
| Proof Techniques for Cryptographic Protocols | p. 25 |
| Type Structure for Low-Level Programming Languages | p. 40 |
| Real Computations with Fake Numbers | p. 55 |
| A Model for Associative Memory, a Basis for Thinking and Consciousness | p. 74 |
| Numerical Integration with Exact Real Arithmetic | p. 90 |
| Observations about the Nature and State of Computer Science (Keynote Address) | p. 105 |
| DNA Computing: New Ideas of Paradigms | p. 106 |
| Online Data Structures in External Memory | p. 119 |
| From Computational Learning Theory to Discovery Science | p. 134 |
| Bounded Depth Arithmetic Circuits: Counting and Closure | p. 149 |
| Parametric Temporal Logic for "Model Measuring" | p. 159 |
| Communicating Hierarchical State Machines | p. 169 |
| Small Pseudo-Random Sets Yield Hard Functions: New Tight Explicit Lower Bounds for Branching Programs | p. 179 |
| General Morphisms of Petri Nets | p. 190 |
| On Some Tighter Inapporximability Results | p. 200 |
| Decomposition and Composition of Timed Automata | p. 210 |
| New Applications of the Incompressibility Method | p. 220 |
| Mobility Types for Mobile Ambients | p. 230 |
| Protein Folding, the Levinthal Paradox and Rapidly Mixing Markov Chains | p. 240 |
| Decidable Fragments of Simultaneous Rigid Reachability | p. 250 |
| Text Compression Using Antidictionaries | p. 261 |
| Non-interactive Zero-Knowledge: A Low-Randomness Characterization of NP | p. 271 |
| Timed Alternating Tree Automata: The Automata-Theoretic Solution to the TCTL Model Checking Problem | p. 281 |
| Space-Time Tradeoffs for Graph Properties | p. 291 |
| Boundedness of Reset P/T Nets | p. 301 |
| Two-Way Finite State Transducers and Monadic Second-Order Logic | p. 311 |
| Partially Ordered Regular Languages for Graph Queries | p. 321 |
| Deciding First-Order Properties of Locally Tree-Decomposable Graphs | p. 331 |
| Comparison of Process Algebra Equivalences Using Formats | p. 341 |
| Compact Routing Tables for Graphs of Bounded Genus | p. 351 |
| Computing LOGCFL Certificates | p. 361 |
| Efficient Techniques for Maintaining Multidimensional Keys in Linked Data Structures | p. 372 |
| On the Complements of Partial k-Trees | p. 382 |
| Approximation Results for Kinetic Variants of TSP | p. 392 |
| Distributed Probabilistic Polling and Applications to Proportionate Agreement | p. 402 |
| Bisimulation Equivalence Is Decidable for Normed Process Algebra | p. 412 |
| A Framework for Decidable Metrical Logics | p. 422 |
| On the Power of Las Vegas II. Two-Way Finite Automata | p. 433 |
| Stable Marriage with Incomplete Lists and Ties | p. 443 |
| Average-Case Complexity of Shellsort (Preliminary Version) | p. 453 |
| Linear-Time Construction of Two-Dimensional Suffix Trees | p. 463 |
| A Connection between the Star Problem and the Finite Power Property in Trace Monoids | p. 473 |
| Two Techniques in the Area of the Star Problem | p. 483 |
| Approximations by OBDDs and the Variable Ordering Problem | p. 493 |
| Simulation Preorder on Simple Process Algebras | p. 503 |
| Solos in Concert | p. 513 |
| Shortest Anisotropic Paths on Terrains | p. 524 |
| Relations Between Local and Global Periodicity of Words | p. 534 |
| Efficient Merging, Construction, and Maintenance of Evolutionary Trees | p. 544 |
| Formalizing a Lazy Substitution Proof System for [mu]-calculus in the Calculus of Inductive Constructions | p. 554 |
| Leader Election by d Dimensional Cellular Automata | p. 565 |
| New Upper Bounds for MaxSat | p. 575 |
| Polynomial and Rational Evaluation and Interpolation (with Structured Matrices) | p. 585 |
| Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time | p. 595 |
| Finite Automata with Generalized Acceptance Criteria | p. 605 |
| A Variant of the Arrow Distributed Directory with Low Average Complexity | p. 615 |
| Closed Freyd- and [kappa]-categories | p. 625 |
| Typed Exceptions and Continuations Cannot Macro-Express Each Other | p. 635 |
| Automata, Power Series, and Coinduction: Taking Input Derivatives Seriously | p. 645 |
| Accessing Multiple Sequences Through Set Associative Caches | p. 655 |
| T(A) = T(B)? | p. 665 |
| Many-Valued Logics and Holographic Proofs | p. 676 |
| On the Complexity and Inapproximability of Shortest Implicant Problems | p. 687 |
| The Wave Propagator Is Turing Computable | p. 697 |
| An FPTAS for Agreeably Weighted Variance on a Single Machine | p. 707 |
| Erratum: Bulk-Synchronous Parallel Multiplication of Boolean Matrices | p. 717 |
| Author Index | p. 719 |
| Table of Contents provided by Blackwell. All Rights Reserved. |
