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

Front Cover
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.
 

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
Author Index
628
Copyright

Other editions - View all

Common terms and phrases