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

This volume contains the proceedings of the LATIN 2000 International Conference (LatinAmerican Theoretical INformatics), to be held in Punta del Este, Uruguay, April 10-14, 2000. This is the fourth event in the series following Sao ~ Paulo, Brazil (1992), Valparaíso, Chile (1995), and Campinas, Brazil (1998). LATIN has established itself as a fully refereed conference for theoretical computer science research in Latin America. It has also strengthened the ties between local and international scientific communities. We believe that this volume reflects the breadth and depth of this interaction. We received 87 submissions, from 178 different authors in 26 different countries. Eachpaperwasassignedtothreeprogramcommitteemembers.TheProgramCommittee selected 42 papers based on approximately 260 referee reports. In addition to these contributed presentations, the conference included six invited talks. The assistance of many organizations and individuals was essential for the success ofthismeeting.Wewouldliketothankallofoursponsorsandsupportingorganizations. Ricardo Baeza-Yates, Claudio Lucchesi, Arnaldo Moura, and Imre Simon provided - sightful advice and shared with us their experiences as organizers of previous LATIN meetings. Joaquín Goyoaga and Patricia Corbo helped in the earliest stages of the - ganization in various ways, including finding Uruguayan sources of financial support. SeCIU(ServicioCentraldeInformatica ́ Universitario, UniversidaddelaRepublica) ́ p- vided us with the necessary communication infrastructure. The meeting of the program committee was hosted by the Instituto de Matematica ́ e Estat stica, í Universidade de Sao ~ Paulo, which also provided us with the Intranet site for discussions among PC members. 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. Frontmatter Random Structures and Algorithms Algorithmic Aspects of Regularity Small Maximal Matchings in Random Graphs Some Remarks on Sparsely Connected Isomorphism-Free Labeled Graphs Analysis of Edge Deletion Processes on Faulty Random Regular Graphs Equivalent Conditions for Regularity ~(Extended Abstract) Algorithms I Cube Packing Approximation Algorithms for Flexible Job Shop Problems Emerging Behavior as Binary Search Trees Are Symmetrically Updated The LCA Problem Revisited Combinatorial Designs Optimal and Pessimal Orderings of Steiner Triple Systems in Disk Arrays Rank Inequalities for Packing Designs and Sparse Triple Systems The Anti-Oberwolfach Solution: Pancyclic 2-Factorizations of Complete Graphs Web Graph, Graph Theory I Graph Structure of the Web: A Survey Polynomial Time Recognition of Clique-Width $\leq$~ 3 Graphs On Dart-Free Perfectly Contractile Graphs Extended Abstract Graph Theory II Edge Colouring Reduced Indifference Graphs Two Conjectures on the Chromatic Polynomial Finding Skew Partitions Efficiently Competitive Analysis, Complexity On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract) Almost {\itshape k}-Wise Independence and Hard Boolean Functions Improved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function Algorithms II Multi-parameter Minimum Spanning Trees Linear Time Recognition of Optimal L-Restricted Prefix Codes Uniform Multi-hop All-to-All Optical Routings in Rings A Fully Dynamic Algorithm for Distributed Shortest Paths Computational Number Theory, Cryptography Integer Factorization and Discrete Logarithms Communication Complexity and Fourier Coefficients of the Diffie--Hellman Key Quintic Reciprocity and Primality Test for Numbers of the Form $M~=~A5^{n} \pm ~\omega_{n}$ Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography Analysis of Algorithms I Average-Case Analysis of Rectangle Packings Heights in Generalized Tries and PATRICIA Tries On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths Extended Abstract Algebraic Algorithms Subresultants Revisited A Unifying Framework for the Analysis of a Class of Euclidean Algorithms Worst-Case Complexity of the Optimal LLL Algorithm Computability Iteration Algebras Are Not Finitely Axiomatizable Undecidable Problems in Unreliable Computations Automata, Formal Languages Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers Unambiguous B\"{u}chi Automata Linear Time Language Recognition on Cellular Automata with Restricted Communication Logic, Programming Theory From Semantics to Spatial Distribution On the Expressivity and Complexity of Quantitative Branching-Time Temporal Logics A Theory of Operational Equivalence for Interaction Nets Analysis of Algorithms II Run Statistics for Geometrically Distributed Random Variables Generalized Covariances of Multi-dimensional Brownian Excursion Local Times Combinatorics of Geometrically Distributed Random Variables: Length of Ascending Runs Backmatter 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