LATIN 2010: Theoretical Informatics

The papers contained in this volume were presented at the 9th Latin American TheoreticalInformaticsSymposiumheldattheBenitoJü arezUniversityofO- aca, Oaxaca City, M¿ exico, April 19-23, 2010. The LATIN series of conferences was launched in 1992 to foster the interaction between the Latin American t- oretical computer science community and computer scientists around the world. LATIN 2010wasthe ninth ofa series,after SaoPaulo,Brazil(1992);Valparaiso, Chile (1995); Campinas, Brazil (1998); Punta del Este, Uruguay (2000); C- cun, Mexico (2002); Buenos Aires, Argentina (2004); Valdivia, Chile (2006) and B¿ uzios, Rio de Janeiro, Brazil (2008). From the 155 submissions, the Program Committee selected 56 papers for presentation at the conference. The selectionofpaperswasbasedonoriginality, quality, and relevance to theoretical computer science. It is expected that most of these papers will appear in a more complete and polished form in scienti?c journalsinthefuture.Inadditiontothecontributedpapers,thisvolumecontains the abstracts of four invited plenary talks given at the conference by Cristopher Moore, Piotr Indyk, Sergio Rajsbaum, and Leslie Valiant. A special session on the life and work of the late Imre Simon was held. Prof. Simon played a key role in the development of theoretical computer science in Latin American as well as theLATINconference.ThissessionhadcontributionsfromRicardoBaeza-Yates, John Brzozowski, Volker Diekert, and Jacques Sakarovitch.