LEADER 08198nam 22008055 450 001 996465411003316 005 20200706103223.0 010 $a1-280-30822-2 010 $a9786610308224 010 $a3-540-24698-3 024 7 $a10.1007/b95852 035 $a(CKB)1000000000212322 035 $a(DE-He213)978-3-540-24698-5 035 $a(SSID)ssj0000189574 035 $a(PQKBManifestationID)11184452 035 $a(PQKBTitleCode)TC0000189574 035 $a(PQKBWorkID)10156577 035 $a(PQKB)11494502 035 $a(MiAaPQ)EBC3087252 035 $a(PPN)155184172 035 $a(EXLCZ)991000000000212322 100 $a20121227d2004 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aLATIN 2004: Theoretical Informatics$b[electronic resource] $e6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings /$fedited by Martin Farach-Colton 205 $a1st ed. 2004. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2004. 215 $a1 online resource (XVI, 632 p.) 225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v2976 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-21258-2 320 $aIncludes bibliographical references at the end of each chapters and index. 327 $aInvited 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. 330 $aThis 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. 410 0$aLecture Notes in Computer Science,$x0302-9743 ;$v2976 606 $aComputers 606 $aAlgorithms 606 $aData structures (Computer science) 606 $aComputer logic 606 $aNumerical analysis 606 $aTheory of Computation$3https://scigraph.springernature.com/ontologies/product-market-codes/I16005 606 $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021 606 $aData Structures$3https://scigraph.springernature.com/ontologies/product-market-codes/I15017 606 $aComputation by Abstract Devices$3https://scigraph.springernature.com/ontologies/product-market-codes/I16013 606 $aLogics and Meanings of Programs$3https://scigraph.springernature.com/ontologies/product-market-codes/I1603X 606 $aNumeric Computing$3https://scigraph.springernature.com/ontologies/product-market-codes/I1701X 615 0$aComputers. 615 0$aAlgorithms. 615 0$aData structures (Computer science). 615 0$aComputer logic. 615 0$aNumerical analysis. 615 14$aTheory of Computation. 615 24$aAlgorithm Analysis and Problem Complexity. 615 24$aData Structures. 615 24$aComputation by Abstract Devices. 615 24$aLogics and Meanings of Programs. 615 24$aNumeric Computing. 676 $a004 702 $aFarach-Colton$b Martin$4edt$4http://id.loc.gov/vocabulary/relators/edt 712 12$aLatin American Symposium on Theoretical Informatics 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996465411003316 996 $aLATIN 2004: Theoretical Informatics$92204563 997 $aUNISA