内容

目次

Invited Talks and Tutorials.- Phase Transitions in Computer Science.- The Internet, the Web, and Algorithms.- Erd?s Magic.- Open Problems in Computational Geometry.- Quantum Algorithms.- Testing and Checking of Finite State Systems.- From Algorithms to Cryptography Tutorial.- Dihomotopy as a Tool in State Space Analysis Tutorial.- Regular Contributions.- Algorithms for Local Alignment with Length Constraints*.- An Algorithm That Builds a Set of Strings Given Its Overlap Graph.- Conversion between Two Multiplicatively Dependent Linear Numeration Systems.- Star Height of Reversible Languages and Universal Automata.- Weakly Iterated Block Products of Finite Monoids.- The Hidden Number Problem in Extension Fields and Its Applications.- The Generalized Weil Pairing and the Discrete Logarithm Problem on Elliptic Curves.- Random Partitions with Non Negative rth Differences.- Beta-Expansions for Cubic Pisot Numbers.- Facility Location Constrained to a Polygonal Domain.- A Deterministic Polynomial Time Algorithm for Heilbronn’s Problem in Dimension Three.- A Metric Index for Approximate String Matching.- On Maximal Suffices and Constant-Space Linear-Time Versions of KMP Algorithm.- On the Power of BFS to Determine a Graphs Diameter.- k-pseudosnakes in Large Grids.- L(2, 1)-Coloring Matrogenic Graphs.- Pipeline Transportation of Petroleum Products with No Due Dates.- Ancestor Problems on Pure Pointer Machines.- Searching in Random Partially Ordered Sets.- Packing Arrays.- Generalized Shannon Code Minimizes the Maximal Redundancy.- An Improved Algorithm for Sequence Comparison with Block Reversals.- Pattern Matching and Membership for Hierarchical Message Sequence Charts.- Improved Exact Algorithms for Max-Sat.- Characterising Strong Normalisation for Explicit Substitutions.- Parameters in Pure Type Systems.- Category, Measure, Inductive Inference: A Triality Theorem and Its Applications.- Verification of Embedded Reactive Fiffo Systems.- Electronic Jury Voting Protocols.- Square Roots Modulo p.- Finding Most Sustainable Paths in Networks with Time-Dependent Edge Reliabilities.- Signals for Cellular Automata in Dimension 2 or Higher.- Holographic Trees.- On the Spanning Ratio of Gabriel Graphs and ?-skeletons.- In-Place Planar Convex Hull Algorithms.- The Level Ancestor Problem Simplified.- Flow Metrics.- On Logical Descriptions of Regular Languages.- Computing Boolean Functions from Multiple Faulty Copies of Input Bits.- Inapproximability Results on Stable Marriage Problems.- Tight Bounds for Online Class-Constrained Packing.- On-line Algorithms for Edge-Disjoint Paths in Trees of Rings.- Massive Quasi-Clique Detection.- Improved Tree Decomposition Based Algorithms for Domination-like Problems.