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

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.