LATIN 2008: Theoretical Informatics : 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings

The Latin American Theoretical INformatics Symposium (LATIN) is becoming a traditional and high-quality conference on the Theory of Computing. Previous conferenceshavebeenorganizedtwiceinBrazil:S" aoPaulo(1992)andCampinas (1998); twice in Chile: Valpara' ?so (1995) and Valdivia (2006); once in Uruguay: Punta del Este (2000); once in Mexico: Cancun (2002); and once in Argentina: Buenos Aires (2004). This volume contains the proceedings of the 8th Latin American Theore- cal INformatics Symposium (LATIN 2008), which was held in Buzio ' s, Rio de Janeiro, Brazil, April 7-11, 2008. Atotalof242paperswerereviewedbytheprogramcommittee.Amongthem, 66 were selected for presentation at the conference. The selection was based on the papers' originality, quality and relevance to Theoretical Computer Science. This volume also contains the extended abstract associated with the invited talk of Wojciech Szpankowski. We also had 4 invited talks by Cl' audio Leonardo Lucchesi, Eva Tardos, Moni Naor and Robert Tarjan. We wouldlike to thank allmembers ofthe PCfortheir thoroughwork,which resultedinagoodselectionofpapers;themembersoftheSteeringCommitteefor their insightfuladviceandforsharingtheir experiencewithus;andthe members of our community who served as referees. Inaddition,wethankalloursponsors,Microsoft,UOL,IFIP,HP,Yahoo!, FAPERJ, CNPq and CAPES, and Springer for their continuous support.