Automata, Languages and Programming

Invited Talks.- Generating Hard Instances of the Short Basis Problem.- Wide Area Computation.- Proof Techniques for Cryptographic Protocols.- Type Structure for Low-Level Programming Languages.- Real Computations with Fake Numbers.- A Model for Associative Memory, a Basis for Thinking and Consciousness.- Numerical Integration with Exact Real Arithmetic.- Observations about the Nature and State of Computer Science.- DNA Computing: New Ideas and Paradigms.- Online Data Structures in External Memory.- From Computational Learning Theory to Discovery Science.- Contributed Papers.- Bounded Depth Arithmetic Circuits: Counting and Closure.- Parametric Temporal Logic for “Model Measuring”.- Communicating Hierarchical State Machines.- Small Pseudo-Random Sets Yield Hard Functions: New Tight Explicit Lower Bounds for Branching Programs.- General Morphisms of Petri Nets (Extended Abstract).- On Some Tighter Inapproximability Results (Extended Abstract).- Decomposition and Composition of Timed Automata.- New Applications of the Incompressibility Method (Extended Abstract).- Mobility Types for Mobile Ambients.- Protein Folding, the Levinthal Paradox and Rapidly Mixing Markov Chains.- Decidable Fragments of Simultaneous Rigid Reachability.- Text Compression Using Antidictionaries.- Non-interactive Zero-Knowledge: A Low-Randomness Characterization of NP (Extended Abstract).- Timed Alternating Tree Automata: The Automata-Theoretic Solution to the TCTL Model Checking Problem.- Space-Time Tradeoffs for Graph Properties.- Boundedness of Reset P/T Nets.- Two-way finite state transducers and monadic second-order logic.- Partially Ordered Regular Languages for Graph Queries.- Deciding First-Order Properties of Locally Tree-Decomposable Graphs.- Comparison of Process Algebra Equivalences Using Formats.- Compact Routing Tables for Graphs of Bounded Genus (Extended Abstract).- Computing LOGCFL Certificates.- Efficient Techniques for Maintaining Multidimensional Keys in Linked Data Structures (Extended Abstract).- On the Complements of Partial k-Trees.- Approximation Results for Kinetic Variants of TSP.- Distributed Probabilistic Polling and Applications to Proportionate Agreement.- Bisimulation Equivalence Is Decidable for Normed Process Algebra (Extended abstract).- A Framework for Decidable Metrical Logics.- On the Power of Las Vegas II. Two-Way Finite Automata.- Stable Marriage with Incomplete Lists and Ties.- Average-Case Complexity of Shellsort (Preliminary Version).- Linear-Time Construction of Two-Dimensional Suffix Trees (Extended Abstract).- A Connection between the Star Problem and the Finite Power Property in Trace Monoids (Extended Abstract).- Two Techniques in the Area of the Star Problem.- Approximations by OBDDs and the Variable Ordering Problem.- Simulation Preorder on Simple Process Algebras.- Solos in Concert.- Shortest Anisotropic Paths on Terrains.- Relations between Local and Global Periodicity of Words (Extended Abstract).- Efficient Merging, Construction, and Maintenance of Evolutionary Trees.- Formalizing a Lazy Substitution Proof System for ?-Calculus in the Calculus of Inductive Constructions.- Leader Election by d Dimensional Cellular Automata.- New Upper Bounds for MaxSat.- Polynomial and Rational Evaluation and Interpolation (with Structured Matrices) ?.- Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time.- Finite Automata with Generalized Acceptance Criteria.- A Variant of the Arrow Distributed Directory with Low Average Complexity (Extended Abstract).- Closed Freyd- and ?-categories.- Typed Exceptions and Continuations Cannot Macro-Express Each Other.- Automata, Power Series, and Coinduction: Taking Input Derivatives Seriously (Extended Abstract).- Accessing Multiple Sequences Through Set Associative Caches.- T(A) = T(B)?.- Many-Valued Logics and Holographic Proofs.- On the Complexity and Inapproximability of Shortest Implicant Problems.- The Wave Propagator Is Turing Computable.- An FPTAS for Agreeably Weighted Variance on a Single Machine (Extended Abstract).- Erratum: Bulk-Synchronous Parallel Multiplication of Boolean Matrices.