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

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 -