LATIN 2000: Theoretical Informatics: 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000 Proceedings (Lecture Notes in Computer Science, 1776)

This book constitutes the refereed proceedings of the 4th International Conference, Latin American Theoretical Informatics, LATIN 2000, held in Punta del Est, Uruguay, in April 2000. The 42 revised papers presented were carefully reviewed and selected from a total of 87 submissions from 26 countries. Also included are abstracts or full papers of several invited talks. The papers are organized in topical sections on random structures and algorithms, complexity, computational number theory and cryptography, algebraic algorithms, computability, automata and formal languages, and logic and programming theory. Algorithmic Aspects Of Regularity / Y. Kohayakawa And V. Rodl -- Small Maximal Matchings In Random Graphs / Michele Zito -- Some Remarks On Sparsely Connected Isomorphism-free Labeled Graphs / Vlady Ravelomanana And Lays Thimonier -- Analysis Of Edge Deletion Processes On Faulty Random Regular Graphs / Andreas Goerdt And Mike Molloy -- Equivalent Conditions For Regularity / Y. Kohayakawa, V. Rodl And J. Skokan -- Cube Packing / F. K. Miyazawa And Y. Wakabayashi -- Approximation Algorithms Fro Flexible Job Shop Problems / Klaus Jansen, Monaldo Mastrolilli And Roberto Solis-oba -- Emerging Behavior As Binary Search Trees Are Symmetrically Updated / Stephen Taylor -- The Lca Problem Revisited / Michael A. Bender And Martin Farach-colton -- Optimal And Pessimal Orderings Of Steiner Triple Systems In Disk Arrays / Myra B. Cohen And Charles J. Colbourn -- Rank Inequalities For Packing Designs And Sparse Triple Systems / Lucia Moura --^ The Anti-oberwolfach Solution: Pancyclic 2-factorizations Of Complete Graphs / Brett Stevens -- Graph Structure Of The Web: A Survey / Prabhakar Raghavan -- Polynomial Time Recognition Of Clique-width [actual Symbol Not Reproducible] Graphs / Derek G. Corneil, Michel Habib And Jean-marc Lanlignel / [et Al.] -- On Dart-free Perfectly Contractile Graphs / Claudia Linhares Sales And Frederic Maffray -- Edge Colouring Reduced Indifference Graphs / Celina M. H. De Figueiredo, Celia Picinin De Mello And Carmen Ortiz -- Two Conjectures On The Chromatic Polynomial / David Avis, Caterina De Simone And Paolo Nobili -- Finding Skew Partitions Efficiently / Celina M. H. De Figueiredo, Sulamita Klein And Yoshiharu Kohayakawa / [et Al.] -- On The Competitive Theory And Practice Of Portfolio Selection / Allan Borodin, Ran El-yaniv And Vincent Gogan -- Almost K-wise Independence And Hard Boolean Functions / Valentine Kabanets --^ Improved Upper Bounds On The Simultaneous Messages Complexity Of The Generalized Addressing Function / Andris Ambainis And Satyanarayana V. Lokam -- Multi-parameter Minimum Spanning Trees / David Fernandez-baca -- Linear Time Recognition Of Optimal L-restricted Prefix Codes / Ruy Luiz Milidiu And Eduardo Sany Laber -- Uniform Multi-hop All-to-all Optical Routings In Rings / Jaroslav Opatrny -- A Fully Dynamic Algorithm For Distributed Shortest Paths / Serafino Cicerone, Gabriele Di Stefano And Daniele Frigioni / [et Al.] -- Integer Factorization And Discrete Logarithms / Andrew Odlyzko -- Communication Complexity And Fourier Coefficients Of The Diffie-hellman Key / Igor E. Shparlinski -- Quintic Reciprocity And Primality Test For Numbers Of The Form [actual Symbol Not Reproducible] / Pedro Berrizbeitia, Mauricio Odreman Vera And Juan Tena Ayuso -- Determining The Optimal Contrast For Secret Sharing Schemes In Visual Cryptography / Matthias Krause And Hans Ulrich Simon --^ Average-case Analysis Of Rectangle Packings / E. G. Coffman, Jr., George S. Lueker And Joel Spencer / [et Al.] -- Heights In Generalized Tries And Patricia Tries / Charles Knessl And Wojciech Szpankowski -- On The Complexity Of Routing Permutations On Trees By Arc-disjoint Paths / D. Barth, S. Corteel And A. Denise / [et Al.] -- Subresultants Revisited / Joachim Von Zur Gathen And Thomas Lucking -- A Unifying Framework For The Analysis Of A Class Of Euclidean Algorithms / Brigite Vallee -- Worst-case Complexity Of The Optimal Lll Algorithm / Ali Akhavi -- Iteration Algebras Are Not Finitely Axiomatizable / Stephen L. Bloom And Zoltan Esik -- Undecidable Problems In Unreliable Computations / Richard Mayr -- Equations In Free Semigroups With Anti-involution And Their Relation To Equations In Free Groups / Claudio Gutierrez --^ Squaring Transducers: An Efficient Procedure For Deciding Functionality And Sequentiality Of Transducers / Marie-pierre Beal, Olivier Carton And Christopher Prieur / [et Al.] -- Unambiguous Buchi Automata / Olivier Carton And Max Michel -- Linear Time Language Recognition On Cellular Automata With Restricted Communication / Thomas Worsch -- From Semantics To Spatial Distribution / Luis R. Sierra Abbate, Pedro R. D'argenio And Juan V. Echague -- On The Expressivity And Complexity Of Quantitative Branching-time Temporal Logics / F. Laroussinie, Ph. Schnoebelen And M. Turuani -- A Theory Of Operational Equivalence For Interaction Nets / Maribel Fernandez And Ian Mackie -- Run Statistics For Geometrically Distributed Random Variables / Peter Grabner, Arnold Knopfmacher And Helmut Prodinger -- Generalized Covariances Of Multi-dimensional Brownian Excursion Local Times / Guy Louchard -- Combinatorics Of Geometrically Distributed Random Variables: Length Of Ascending Runs / Helmut Prodinger. Gastón H. Gonnet, Daniel Panario, Alfredo Viola (eds.). Includes Bibliographical References And Index. Front Matter....Pages - Algorithmic Aspects of Regularity....Pages 1-17 Small Maximal Matchings in Random Graphs....Pages 18-27 Some Remarks on Sparsely Connected Isomorphism-Free Labeled Graphs....Pages 28-37 Analysis of Edge Deletion Processes on Faulty Random Regular Graphs....Pages 38-47 Equivalent Conditions for Regularity (Extended Abstract)....Pages 48-57 Cube Packing....Pages 58-67 Approximation Algorithms for Flexible Job Shop Problems....Pages 68-77 Emerging Behavior as Binary Search Trees Are Symmetrically Updated....Pages 78-87 The LCA Problem Revisited....Pages 88-94 Optimal and Pessimal Orderings of Steiner Triple Systems in Disk Arrays....Pages 95-104 Rank Inequalities for Packing Designs and Sparse Triple Systems....Pages 105-114 The Anti-Oberwolfach Solution: Pancyclic 2-Factorizations of Complete Graphs....Pages 115-122 Graph Structure of the Web: A Survey....Pages 123-125 Polynomial Time Recognition of Clique-Width ≤ 3 Graphs....Pages 126-134 On Dart-Free Perfectly Contractile Graphs Extended Abstract....Pages 135-144 Edge Colouring Reduced Indifference Graphs....Pages 145-153 Two Conjectures on the Chromatic Polynomial....Pages 154-162 Finding Skew Partitions Efficiently....Pages 163-172 On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract)....Pages 173-196 Almost k -Wise Independence and Hard Boolean Functions....Pages 197-206 Improved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function....Pages 207-216 Multi-parameter Minimum Spanning Trees....Pages 217-226 Linear Time Recognition of Optimal L-Restricted Prefix Codes....Pages 227-236 Uniform Multi-hop All-to-All Optical Routings in Rings....Pages 237-246 A Fully Dynamic Algorithm for Distributed Shortest Paths....Pages 247-257 Integer Factorization and Discrete Logarithms....Pages 258-258 Communication Complexity and Fourier Coefficients of the Diffie–Hellman Key....Pages 259-268 Quintic Reciprocity and Primality Test for Numbers of the Form $M~=~A5^{n} \pm ~\omega_{n}$ ....Pages 269-279 Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography....Pages 280-291 Average-Case Analysis of Rectangle Packings....Pages 292-297 Heights in Generalized Tries and PATRICIA Tries....Pages 298-307 On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths Extended Abstract....Pages 308-317 Subresultants Revisited....Pages 318-342 A Unifying Framework for the Analysis of a Class of Euclidean Algorithms....Pages 343-354 Worst-Case Complexity of the Optimal LLL Algorithm....Pages 355-366 Iteration Algebras Are Not Finitely Axiomatizable....Pages 367-376 Undecidable Problems in Unreliable Computations....Pages 377-386 Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups....Pages 387-396 Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers....Pages 397-406 Unambiguous Büchi Automata....Pages 407-416 Linear Time Language Recognition on Cellular Automata with Restricted Communication....Pages 417-426 From Semantics to Spatial Distribution....Pages 427-436 On the Expressivity and Complexity of Quantitative Branching-Time Temporal Logics....Pages 437-446 A Theory of Operational Equivalence for Interaction Nets....Pages 447-456 Run Statistics for Geometrically Distributed Random Variables....Pages 457-462 Generalized Covariances of Multi-dimensional Brownian Excursion Local Times....Pages 463-472 Combinatorics of Geometrically Distributed Random Variables: Length of Ascending Runs....Pages 473-482 Back Matter....Pages -