Latin 2002: Theoretical Informatics : 5th Latin American Symposium Cancun, Mexico, April 3-6, 2002 : Proceedings

by Latin American Symposium on Theoretical Informatics 2002 Cancun, Mexi; Rajsbaum, Sergio; Rajsbaum, Sergio

• ISBN13: 9783540434009
• ISBN10: 3540434003
• Format: Paperback
• Copyright: 2002-05-01
• Publisher: Springer Verlag

Summary

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.

Table of Contents

Invited Talks and Tutorials
Phase Transitions in Computer Science	1	(1)
Jennifer Chayes
The Internet, the Web, and Algorithms	2	(1)
Christos H. Papadimitriou
Erdos Magic	3	(1)
Joel Spencer
Open Problems in Computational Geometry	4	(8)
Jorge Urrutia
Quantum Algorithms	12	(2)
Umesh Vazirani
Testing and Checking of Finite State Systems	14	(1)
Mihalis Yannakakis
From Algorithms to Cryptography	15	(1)
Fabrizio Luccio
Linda Pagli
Dihomotopy as a Tool in State Space Analysis	16	(22)
Eric Goubault
Martin Raussen
Regular Contributions
Algorithms for Local Alignment with Length Constraints	38	(14)
Abdullah N. Arslan
Omer Egecioglu
An Algorithm That Builds a Set of Strings Given Its Overlap Graph	52	(12)
Marila D. V. Braga
Joao Meidanis
Conversion between Two Multiplicatively Dependent Linear Numeration Systems	64	(12)
Christiane Frougny
Star Height of Reversible Languages and Universal Automata	76	(15)
Sylvain Lombardy
Jacques Sakarovitch
Weakly Iterated Block Products of Finite Monoids	91	(14)
Howard Straubing
Denis Therien
The Hidden Number Problem in Extension Fields and Its Applications	105	(13)
Maria Isabel Gonzalez Vasco
Mats Naslund
Igor E. Shparlinski
The Generalized Weil Pairing and the Discrete Logarithm Problem on Elliptic Curves	118	(13)
Theodoulos Garefalakis
Random Partitions with Non Negative rth Differences	131	(10)
Rod Canfield
Sylvie Corteel
Pawel Hitczenko
Beta-Expansions for Cubic Pisot Numbers	141	(12)
Frederique Bassino
Facility Location Constrained to a Polygonal Domain	153	(12)
Prosenjit Bose
Qingda Wang
A Deterministic Polynomial Time Algorithm for Heilbronn's Problem in Dimension Three	165	(16)
Hanno Lefmann
Niels Schmitt
A Metric Index for Approximate String Matching	181	(15)
Edgar Chavez
Gonzalo Navarro
On Maximal Suffices and Constant-Space Linear-Time Versions of KMP Algorithm	196	(13)
Wojciech Rytter
On the Power of BFS to Determine a Graphs Diameter	209	(15)
Derek G. Corneil
Feodor F. Dragan
Ekkehard Kohler
k-pseudosnakes in Large Grids	224	(12)
Martin. Matamala
Erich Prisner
Ivan Rapaport
L(2, 1)-Coloring Matrogenic Graphs	236	(12)
Tiziana Calamoneri
Rossella Petreschi
Pipeline Transportation of Petroleum Products with No Due Dates	248	(15)
Ruy Luiz Milidiu
Artur Alves Pessoa
Eduardo Sany Laber
Ancestor Problems on Pure Pointer Machines	263	(15)
Enrico Pontelli
Desh Ranjan
Searching in Random Partially Ordered Sets	278	(15)
Renato Carmo
Jair Donadelli
Yoshiharu Kohayakawa
Eduardo Laber
Packing Arrays	293	(13)
Brett Stevens
Eric Mendelsohn
Generalized Shannon Code Minimizes the Maximal Redundancy	306	(13)
Michael Drmota
Wojciech Szpankowski
An Improved Algorithm for Sequence Comparison with Block Reversals	319	(7)
S. Muthukrishnan
S. Cenk Sahinalp
Pattern Matching and Membership for Hierarchical Message Sequence Charts	326	(15)
Blaise Genest
Anca Muscholl
Improved Exact Algorithms for MAX-SAT	341	(15)
Jianer Chen
Iyad A. Kanj
Characterising Strong Normalization for Explicit Substitutions	356	(15)
Steffen van Bakel
Mariangiola Dezani-Ciancaglini
Parameters in Pure Type Systems	371	(15)
Roel Bloo
Fairouz Kamareddine
Twan Laan
Rob Nederpelt
Category, Measure, Inductive Inference: A Triality Theorem and Its Applications	386	(14)
Rusins Freivalds
Carl H. Smith
Verification of Embedded Reactive Fiffo Systems	400	(15)
Frederic Herbreteau
Franck Cassez
Alain Finkel
Olivier Roux
Gregoire Sutre
Electronic Jury Voting Protocols	415	(15)
Alejandro Hevia
Marcos Kiwi
Square Roots Modulo p	430	(5)
Gonzalo Tornaria
Finding Most Sustainable Paths in Networks with Time-Dependent Edge Reliabilities	435	(16)
Goran Konjevod
Soohyun Oh
Andrea W. Richo
Signals for Cellular Automata in Dimension 2 or Higher	451	(14)
Jean-Christophe Dubacq
Veronique Terrier
Holographic Trees	465	(14)
Paolo Boldi
Sebastiano Vigna
On the Spanning Ratio of Gabriel Graphs and, β-skeletons	479	(15)
Prosenjit Bose
Luc Devroye
William Evans
David Kirkpatrick
In-Place Planar Convex Hull Algorithms	494	(14)
Herve Bronnimann
John Iacono
Jyrki Katajainen
Pat Morin
Jason Morrison
Godfried Toussaint
The Level Ancestor Problem Simplified	508	(8)
Michael A. Bender
Martin Farach-Colton
Flow Metrics	516	(12)
Claudson F. Bornstein
Santosh Vempala
On Logical Descriptions of Regular Languages	528	(11)
Howard Straubing
Computing Boolean Functions from Multiple Faulty Copies of Input Bits	539	(15)
Mario Szegedy
Xiaomin Chen
Inapproximability Results on Stable Marriage Problems	554	(15)
Magnus Halldorsson
Kazuo Iwamma
Shuichi Miyazaki
Yasufumi Morita
Tight Bounds for Online Class-Constrained Packing	569	(15)
Hadas Shachnai
Tami Tamir
On-line Algorithms for Edge-Disjoint Paths in Trees of Rings	584	(14)
R. Sai Anand
Thomas Erlebach
Massive Quasi-Clique Detection	598	(15)
James Abello
Mauricio G.C. Resende
Sandra Sudarsky
Improved Tree Decomposition Based Algorithms for Domination-like Problems	613	(16)
Jochen Alber
Rolf Niedermeier
Author Index	629