LATIN 2000: Theoretical Informatics 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000 Proceedings

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.

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 ?  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 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 .- 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ü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.