LATIN 2000 : theoretical informatics : 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000 : proceedings
Author(s)
Bibliographic Information
LATIN 2000 : theoretical informatics : 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000 : proceedings
(Lecture notes in computer science, 1776)
Springer, c2000
Available at 34 libraries
  Aomori
  Iwate
  Miyagi
  Akita
  Yamagata
  Fukushima
  Ibaraki
  Tochigi
  Gunma
  Saitama
  Chiba
  Tokyo
  Kanagawa
  Niigata
  Toyama
  Ishikawa
  Fukui
  Yamanashi
  Nagano
  Gifu
  Shizuoka
  Aichi
  Mie
  Shiga
  Kyoto
  Osaka
  Hyogo
  Nara
  Wakayama
  Tottori
  Shimane
  Okayama
  Hiroshima
  Yamaguchi
  Tokushima
  Kagawa
  Ehime
  Kochi
  Fukuoka
  Saga
  Nagasaki
  Kumamoto
  Oita
  Miyazaki
  Kagoshima
  Okinawa
  Korea
  China
  Thailand
  United Kingdom
  Germany
  Switzerland
  France
  Belgium
  Netherlands
  Sweden
  Norway
  United States of America
-
Library, Research Institute for Mathematical Sciences, Kyoto University数研
L/N||LNCS||177600005114
Note
Includes bibliographical references and index
Description and Table of Contents
Description
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),Valparaiso, 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. Joaquin 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, i Universidade de Sao " Paulo, which also provided us with the Intranet site for discussions among PC members.
Table of Contents
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 Buchi 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.
by "Nielsen BookData"