LATIN 2002: Theoretical Informatics: 5th Latin American Symposium Cancun, Mexico, April 3–6, 2002 Proceedings

Phase Transitions in Computer Science....Pages 1-1
The Internet, the Web, and Algorithms....Pages 2-2
Erdős Magic....Pages 3-3
Open Problems in Computational Geometry....Pages 4-11
Quantum Algorithms....Pages 12-13
Testing and Checking of Finite State Systems....Pages 14-14
From Algorithms to Cryptography Tutorial....Pages 15-15
Dihomotopy as a Tool in State Space Analysis Tutorial....Pages 16-37
Algorithms for Local Alignment with Length Constraints * ....Pages 38-51
An Algorithm That Builds a Set of Strings Given Its Overlap Graph....Pages 52-63
Conversion between Two Multiplicatively Dependent Linear Numeration Systems....Pages 64-75
Star Height of Reversible Languages and Universal Automata....Pages 76-90
Weakly Iterated Block Products of Finite Monoids....Pages 91-104
The Hidden Number Problem in Extension Fields and Its Applications....Pages 105-117
The Generalized Weil Pairing and the Discrete Logarithm Problem on Elliptic Curves....Pages 118-130
Random Partitions with Non Negative rth Differences....Pages 131-140
Beta-Expansions for Cubic Pisot Numbers....Pages 141-152
Facility Location Constrained to a Polygonal Domain....Pages 153-164
A Deterministic Polynomial Time Algorithm for Heilbronn’s Problem in Dimension Three....Pages 165-180
A Metric Index for Approximate String Matching....Pages 181-195
On Maximal Suffices and Constant-Space Linear-Time Versions of KMP Algorithm....Pages 196-208
On the Power of BFS to Determine a Graphs Diameter....Pages 209-223
 k -pseudosnakes in Large Grids....Pages 224-235
 L (2, 1)-Coloring Matrogenic Graphs....Pages 236-247
Pipeline Transportation of Petroleum Products with No Due Dates....Pages 248-262
Ancestor Problems on Pure Pointer Machines....Pages 263-277
Searching in Random Partially Ordered Sets....Pages 278-292
Packing Arrays....Pages 293-305
Generalized Shannon Code Minimizes the Maximal Redundancy....Pages 306-318
An Improved Algorithm for Sequence Comparison with Block Reversals....Pages 319-325
Pattern Matching and Membership for Hierarchical Message Sequence Charts....Pages 326-340
Improved Exact Algorithms for Max-Sat....Pages 341-355
Characterising Strong Normalisation for Explicit Substitutions....Pages 356-370
Parameters in Pure Type Systems....Pages 371-385
Category, Measure, Inductive Inference: A Triality Theorem and Its Applications....Pages 386-399
Verification of Embedded Reactive Fiffo Systems....Pages 400-414
Electronic Jury Voting Protocols....Pages 415-429
Square Roots Modulo p ....Pages 430-434
Finding Most Sustainable Paths in Networks with Time-Dependent Edge Reliabilities....Pages 435-450
Signals for Cellular Automata in Dimension 2 or Higher....Pages 451-464
Holographic Trees....Pages 465-478
On the Spanning Ratio of Gabriel Graphs and β-skeletons....Pages 479-493
In-Place Planar Convex Hull Algorithms....Pages 494-507
The Level Ancestor Problem Simplified....Pages 508-515
Flow Metrics....Pages 516-527
On Logical Descriptions of Regular Languages....Pages 528-538
Computing Boolean Functions from Multiple Faulty Copies of Input Bits....Pages 539-553
Inapproximability Results on Stable Marriage Problems....Pages 554-568
Tight Bounds for Online Class-Constrained Packing....Pages 569-583
On-line Algorithms for Edge-Disjoint Paths in Trees of Rings....Pages 584-597
Massive Quasi-Clique Detection....Pages 598-612
Improved Tree Decomposition Based Algorithms for Domination-like Problems....Pages 613-627