Automata, Languages and Programming

Inhaltsverzeichnis

• 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 EquivalencesUsing 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.
• TypedExceptions 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.