LATIN 2004: Theoretical Informatics: 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004. Proceedings

Mike Paterson (auth.), Martín Farach-Colton (eds.)3540212582, 9783540212584, 9783540246985

This volume contains the proceedings of the Latin American Theoretical Inf- matics (LATIN) conference that was held in Buenos Aires, Argentina, April 5–8, 2004. The LATIN series of symposia was launched in 1992 to foster interactions between the Latin American community and computer scientists around the world. This was the sixth event in the series, following S˜ ao Paulo, Brazil (1992), Valparaiso, Chile (1995), Campinas, Brazil (1998), Punta del Este, Uruguay (2000), and Cancun, Mexico (2002). The proceedings of these conferences were also published by Springer-Verlag in the Lecture Notes in Computer Science series: Volumes 583, 911, 1380, 1776, and 2286, respectively. Also, as before, we published a selection of the papers in a special issue of a prestigious journal. We received 178 submissions. Each paper was assigned to four program c- mittee members, and 59 papers were selected. This was 80% more than the previous record for the number of submissions. We feel lucky to have been able to build on the solid foundation provided by the increasingly successful previous LATINs. And we are very grateful for the tireless work of Pablo Mart´ ?nez L´ opez, the Local Arrangements Chair. Finally, we thank Springer-Verlag for publishing these proceedings in its LNCS series.

---

Table of contents :
Front Matter….Pages –
Analysis of Scheduling Algorithms for Proportionate Fairness….Pages 1-1
Advances in the Regularity Method….Pages 2-2
Fighting Spam: The Science….Pages 3-4
The Consequences of Imre Simon’s Work in the Theory of Automata, Languages, and Semigroups….Pages 5-5
Querying Priced Information in Databases: The Conjunctive Case….Pages 6-15
Sublinear Methods for Detecting Periodic Trends in Data Streams….Pages 16-28
An Improved Data Stream Summary: The Count-Min Sketch and Its Applications….Pages 29-38
Rotation and Lighting Invariant Template Matching….Pages 39-48
Computation of the Bisection Width for Random d -Regular Graphs….Pages 49-58
Constrained Integer Partitions….Pages 59-68
Embracing the Giant Component….Pages 69-79
Sampling Grid Colorings with Fewer Colors….Pages 80-89
The Complexity of Finding Top-Toda-Equivalence-Class Members….Pages 90-99
List Partitions of Chordal Graphs….Pages 100-108
Bidimensional Parameters and Local Treewidth….Pages 109-118
Vertex Disjoint Paths on Clique-Width Bounded Graphs….Pages 119-128
On Partitioning Interval and Circular-Arc Graphs into Proper Interval Subgraphs with Applications….Pages 129-140
Collective Tree Exploration….Pages 141-151
Off-Centers: A New Type of Steiner Points for Computing Size-Optimal Quality-Guaranteed Delaunay Triangulations….Pages 152-161
Space-Efficient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time….Pages 162-171
A Geometric Approach to the Bisection Method….Pages 172-180
Improved Linear Expected-Time Algorithms for Computing Maxima….Pages 181-192
A Constant Approximation Algorithm for Sorting Buffers….Pages 193-202
Approximation Schemes for a Class of Subset Selection Problems….Pages 203-211
Finding k -Connected Subgraphs with Minimum Average Weight….Pages 212-221
On the (Im)possibility of Non-interactive Correlation Distillation….Pages 222-231
Pure Future Local Temporal Logics Are Expressively Complete for Mazurkiewicz Traces….Pages 232-241
How Expressions Can Code for Automata….Pages 242-251
Automata for Arithmetic Meyer Sets….Pages 252-261
Efficiently Computing the Density of Regular Languages….Pages 262-270
Longest Repeats with a Block of Don’t Cares….Pages 271-278
Join Irreducible Pseudovarieties, Group Mapping, and Kovács-Newman Semigroups….Pages 279-291
Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank….Pages 292-301
Expected Length of the Longest Common Subsequence for Large Alphabets….Pages 302-311
Universal Types and Simulation of Individual Sequences….Pages 312-321
Separating Codes: Constructions and Bounds….Pages 322-328
Encoding Homotopy of Paths in the Plane….Pages 329-338
A Unified Approach to Coding Labeled Trees….Pages 339-348
Cost-Optimal Trees for Ray Shooting….Pages 349-358
Packing Problems with Orthogonal Rotations….Pages 359-368
Combinatorial Problems on Strings with Applications to Protein Folding….Pages 369-378
Measurement Errors Make the Partial Digest Problem NP -Hard….Pages 379-390
Designing Small Keyboards Is Hard….Pages 391-400
Metric Structures in L 1 : Dimension, Snowflakes, and Average Distortion….Pages 401-412
Nash Equilibria via Polynomial Equations….Pages 413-422
Minimum Latency Tours and the k -Traveling Repairmen Problem….Pages 423-433
Server Scheduling in the Weighted ℓ p Norm….Pages 434-443
An Improved Communication-Randomness Tradeoff….Pages 444-454
Distributed Games and Distributed Control for Asynchronous Systems….Pages 455-465
A Simplified and Dynamic Unified Structure….Pages 466-473
Another View of the Gaussian Algorithm….Pages 474-487
Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections….Pages 488-498
Rooted Maximum Agreement Supertrees….Pages 499-508
Complexity of Cycle Length Modularity Problems in Graphs….Pages 509-518
Procedural Semantics for Fuzzy Disjunctive Programs on Residuated Lattices….Pages 519-529
A Proof System and a Decision Procedure for Equality Logic….Pages 530-539
Approximating the Expressive Power of Logics in Finite Models….Pages 540-556
Arithmetic Circuits for Discrete Logarithms….Pages 557-566
On the Competitiveness of AIMD-TCP within a General Network….Pages 567-576
Gathering Non-oblivious Mobile Robots….Pages 577-588
Bisecting and Gossiping in Circulant Graphs….Pages 589-598
Multiple Mobile Agent Rendezvous in a Ring….Pages 599-608
Global Synchronization in Sensornets….Pages 609-624
Back Matter….Pages –