LATIN 2004: Theoretical Informatics : 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings / edited by Martin Farach-Colton.

Format:

Book

Contributor:

Farach-Colton, Martin, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

Lecture notes in computer science 0302-9743 ; 2976.

Lecture Notes in Computer Science, 0302-9743 ; 2976

Language:

English

Subjects (All):

Computers.

Algorithms.

Data structures (Computer science).

Computer logic.

Numerical analysis.

Theory of Computation.

Algorithm Analysis and Problem Complexity.

Data Structures.

Computation by Abstract Devices.

Logics and Meanings of Programs.

Numeric Computing.

Local Subjects:

Theory of Computation.

Algorithm Analysis and Problem Complexity.

Data Structures.

Computation by Abstract Devices.

Logics and Meanings of Programs.

Numeric Computing.

Physical Description:

1 online resource (XVI, 632 pages).

Edition:

First edition 2004.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2004.

System Details:

text file PDF

Summary:

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.

Contents:

Invited Speakers

Analysis of Scheduling Algorithms for Proportionate Fairness

Advances in the Regularity Method

Fighting Spam: The Science

The Consequences of Imre Simon's Work in the Theory of Automata, Languages, and Semigroups

Contributions

Querying Priced Information in Databases: The Conjunctive Case

Sublinear Methods for Detecting Periodic Trends in Data Streams

An Improved Data Stream Summary: The Count-Min Sketch and Its Applications

Rotation and Lighting Invariant Template Matching

Computation of the Bisection Width for Random d-Regular Graphs

Constrained Integer Partitions

Embracing the Giant Component

Sampling Grid Colorings with Fewer Colors

The Complexity of Finding Top-Toda-Equivalence-Class Members

List Partitions of Chordal Graphs

Bidimensional Parameters and Local Treewidth

Vertex Disjoint Paths on Clique-Width Bounded Graphs

On Partitioning Interval and Circular-Arc Graphs into Proper Interval Subgraphs with Applications

Collective Tree Exploration

Off-Centers: A New Type of Steiner Points for Computing Size-Optimal Quality-Guaranteed Delaunay Triangulations

Space-Efficient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time

A Geometric Approach to the Bisection Method

Improved Linear Expected-Time Algorithms for Computing Maxima

A Constant Approximation Algorithm for Sorting Buffers

Approximation Schemes for a Class of Subset Selection Problems

Finding k-Connected Subgraphs with Minimum Average Weight

On the (Im)possibility of Non-interactive Correlation Distillation

Pure Future Local Temporal Logics Are Expressively Complete for Mazurkiewicz Traces

How Expressions Can Code for Automata

Automata for Arithmetic Meyer Sets

Efficiently Computing the Density of Regular Languages

Longest Repeats with a Block of Don't Cares

Join Irreducible Pseudovarieties, Group Mapping, and Kovács-Newman Semigroups

Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank

Expected Length of the Longest Common Subsequence for Large Alphabets

Universal Types and Simulation of Individual Sequences

Separating Codes: Constructions and Bounds

Encoding Homotopy of Paths in the Plane

A Unified Approach to Coding Labeled Trees

Cost-Optimal Trees for Ray Shooting

Packing Problems with Orthogonal Rotations

Combinatorial Problems on Strings with Applications to Protein Folding

Measurement Errors Make the Partial Digest Problem NP-Hard

Designing Small Keyboards Is Hard

Metric Structures in L 1: Dimension, Snowflakes, and Average Distortion

Nash Equilibria via Polynomial Equations

Minimum Latency Tours and the k-Traveling Repairmen Problem

Server Scheduling in the Weighted ? p Norm

An Improved Communication-Randomness Tradeoff

Distributed Games and Distributed Control for Asynchronous Systems

A Simplified and Dynamic Unified Structure

Another View of the Gaussian Algorithm

Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections

Rooted Maximum Agreement Supertrees

Complexity of Cycle Length Modularity Problems in Graphs

Procedural Semantics for Fuzzy Disjunctive Programs on Residuated Lattices

A Proof System and a Decision Procedure for Equality Logic

Approximating the Expressive Power of Logics in Finite Models

Arithmetic Circuits for Discrete Logarithms

On the Competitiveness of AIMD-TCP within a General Network

Gathering Non-oblivious Mobile Robots

Bisecting and Gossiping in Circulant Graphs

Multiple Mobile Agent Rendezvous in a Ring

Global Synchronization in Sensornets.

Other Format:

Printed edition:

ISBN:

978-3-540-24698-5

9783540246985

Access Restriction:

Restricted for use by site license.