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 Agreea
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.