## LATIN 2002: Theoretical Informatics: 5th Latin American Symposium, Cancun, Mexico, April 3-6, 2002, Proceedings, Volume 5This 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Open Problems in Computational Geometry Invited Talk | 4 |

Quantum Algorithms Invited Talk | 12 |

Testing and Checking of Finite State Systems Invited Talk | 14 |

From Algorithms to Cryptography Tutorial | 15 |

Dihomotopy as a Tool in State Space Analysis Tutorial | 16 |

Algorithms for Local Alignment with Length Constraints | 38 |

An Algorithm That Builds a Set of StringsGiven Its Overlap Graph | 52 |

Conversion between Two Multiplicatively Dependent Linear Numeration Systems | 64 |

An Improved Algorithm for Sequence Comparison with Block Reversals | 319 |

Pattern Matching and Membership for Hierarchical Message Sequence Charts | 326 |

Improved Exact Algorithms for MaxSat | 341 |

Characterising Strong Normalisation for Explicit Substitutions | 356 |

Parameters in Pure Type Systems | 371 |

A Triality Theorem and Its Applications | 386 |

Verification of Embedded Reactive Fiffo Systems | 400 |

Electronic Jury Voting Protocols | 415 |

Star Height of Reversible Languages and Universal Automata | 76 |

Weakly Iterated Block Products of Finite Monoids | 91 |

The Hidden Number Problem in Extension Fields and Its Applications | 105 |

The Generalized Weil Pairing and the Discrete Logarithm Problem on Elliptic Curves | 118 |

Random Partitions with Non Negative rth Differences | 131 |

BetaExpansions for Cubic Pisot Numbers | 141 |

Facility Location Constrained to a Polygonal Domain | 153 |

A Deterministic Polynomial Time Algorithm for Heilbronns Problem in Dimension Three Extended Abstract | 165 |

A Metric Index for Approximate String Matching | 181 |

On Maximal Suffices and ConstantSpace LinearTime Versions of KMP Algorithm | 196 |

On the Power of BFS to Determine a Graphs Diameter Extended Abstract | 209 |

kpseudosnakes in Large Grids | 224 |

L2 1Coloring Matrogenic Graphs Extended Abstract | 236 |

Pipeline Transportation of Petroleum Products with No Due Dates | 248 |

Ancestor Problems on Pure Pointer Machines | 263 |

Searching in Random Partially Ordered Sets Extended Abstract | 278 |

Packing Arrays | 293 |

Generalized Shannon Code Minimizes the Maximal Redundancy | 306 |

Square Roots Modulo p | 430 |

Finding Most Sustainable Paths in Networks with TimeDependent Edge Reliabilities | 435 |

Signals for Cellular Automata in Dimension 2 or Higher | 451 |

Holographic Trees | 465 |

On the Spanning Ratio of Gabriel Graphs and βskeletons | 479 |

InPlace Planar Convex Hull Algorithms | 494 |

The Level Ancestor Problem Simplified | 508 |

Flow Metrics | 516 |

On Logical Descriptions of Regular Languages | 528 |

Computing Boolean Functions from Multiple Faulty Copies of Input Bits | 539 |

Inapproximability Results on Stable Marriage Problems | 554 |

Tight Bounds for Online ClassConstrained Packing | 569 |

Online Algorithms for EdgeDisjoint Paths in Trees of Rings | 584 |

Massive QuasiClique Detection | 598 |

Improved Tree Decomposition Based Algorithms for Dominationlike Problems | 613 |

628 | |

### Other editions - View all

### Common terms and phrases

algorithm alignment apply assume automata automaton batch Berlin Heidelberg 2002 clauses colors competitive ratio complexity Computer Science consider constant construction contains convex hull corresponding deﬁned definition denote deterministic algorithm dipaths disjoint distance dominating set edges edit distance elements exists finite finite fields ﬁrst function Gabriel graph given graph G homomorphism induced input integer iteration languages Lemma length linear literal LNCS lower bound maximal maximum metric minimal minimum monoid morphism node NP-hard obtained occurs optimal p-list packing arrays pair parameter partial order partition path period Pisot Pisot number pointer pointer machines points polynomial problem Proc Proof query Rajsbaum random recursive regular languages result semidirect product sequence solution stable matching step strings subgraph subset substring suffix tree Theorem threshold graph tree of rings tuple variables vertex vertices