LATIN 2002: Theoretical Informatics

1. Front Matter

   Pages I-XIII

   PDF

2. Invited Talks and Tutorials

   1. Phase Transitions in Computer Science

      • Jennifer Chayes

      Pages 1-1

   2. The Internet, the Web, and Algorithms

      • Christos H. Papadimitriou

      Pages 2-2

   3. Erdős Magic

      • Joel Spencer

      Pages 3-3

   4. Open Problems in Computational Geometry

      • Jorge Urrutia

      Pages 4-11

   5. Quantum Algorithms

      • Umesh Vazirani

      Pages 12-13

   6. Testing and Checking of Finite State Systems

      • Mihalis Yannakakis

      Pages 14-14

   7. From Algorithms to Cryptography Tutorial

      • Fabrizio Luccio, Linda Pagli

      Pages 15-15

   8. Dihomotopy as a Tool in State Space Analysis Tutorial

      • Éric Goubault, Marti Raussen

      Pages 16-37

3. Regular Contributions

   1. Algorithms for Local Alignment with Length Constraints*

      • Abdullah N. Arslan, Ömer Eğecioğlu

      Pages 38-51

   2. An Algorithm That Builds a Set of Strings Given Its Overlap Graph

      • Marília D. V. Braga, João Meidanis

      Pages 52-63

   3. Conversion between Two Multiplicatively Dependent Linear Numeration Systems

      • Christiane Frougny

      Pages 64-75

   4. Star Height of Reversible Languages and Universal Automata

      • Sylvain Lombardy, Jacques Sakarovitch

      Pages 76-90

   5. Weakly Iterated Block Products of Finite Monoids

      • Howard Straubing, Denis Thérien

      Pages 91-104

   6. The Hidden Number Problem in Extension Fields and Its Applications

      • María Isabel González Vasco, Mats Näslund, Igor E. Shparlinski

      Pages 105-117

   7. The Generalized Weil Pairing and the Discrete Logarithm Problem on Elliptic Curves

      • Theodoulos Garefalakis

      Pages 118-130

   8. Random Partitions with Non Negative rth Differences

      • Rod Canfield, Sylvie Corteel, Pawel Hitczenko

      Pages 131-140

   9. Beta-Expansions for Cubic Pisot Numbers

      • Frédérique Bassino

      Pages 141-152

   10. Facility Location Constrained to a Polygonal Domain

       • Prosenjit Bose, Qingda Wang

       Pages 153-164

   11. A Deterministic Polynomial Time Algorithm for Heilbronn’s Problem in Dimension Three

       • Hanno Lefmann, Niels Schmitt

       Pages 165-180

This book constitutes the refereed proceedings of the 5th International Symposium, Latin American Theoretical Informatics, LATIN 2002, held in Cancun, Mexico, in April 2002.
The 44 revised full papers presented together with a tutorial and 7 abstracts of invited contributions were carefully reviewed and selected from a total of 104 submissions. The papers presented are devoted to a broad range of topics from theoretical computer science and mathematical foundations, with a certain focus on algorithmics and computations related to discrete structures.

• Algorithms
• Code
• Codes
• Combinatorial Approximation
• Computational Mathematics
• Computer
• Graph Computations
• Mathematical Foundations
• Monoid
• Partition
• Programming Theory
• Shannon
• Theoretical Computer Science
• computer science
• geometry
• algorithm analysis and problem complexity
• data structures

• Compaq Cambridge Research Laboratory, One Cambridge Center, Cambridge, USA

  Sergio Rajsbaum

Policies and ethics