Combinatorial Pattern Matching

11th Annual Symposium. CPM 2000, Montreal, Canada, June 21-23, 2000, Proceedings
1. Auflage 2000
ISBN: 978-3-540-67633-1
Verlag: Springer

Buch, Englisch, 426 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 1370 g

Reihe: Lecture Notes in Computer Science

The papers contained in this volumewere presented at the 11thAnnual Sym- sium on CombinatorialPattern Matching, held June 21-23, 2000 at the Univ- sit edeMontr eal. They were selected from 44 abstracts submitted in response to the call for papers. In addition, there were invited lectures by Andrei Broder (AltaVista), Fernando Pereira (AT&T Research Labs), and Ian H. Witten (U- versity of Waikato). The symposium was preceded by a two-day summer school set up to - tract and train young researchers. The lecturers at the school were Greg Butler, ClementLam,andGusGrahne:BLAST!Howdoyousearchsequencedatabases?, DavidBryant:Phylogeny,Ra aeleGiancarlo: Algorithmicaspectsof speech rec- nition, Nadia El-Mabrouk: Genome rearrangement,LaxmiParida: Flexib- pattern discovery, and Ian H. Witten: Adaptive text mining: inferring structure from sequences. Combinatorial Pattern Matching (CPM) addresses issues of searching and matching strings and more complicated patterns such as trees, regular expr- sions graphs, point sets, and arrays. The goal is to derive non-trivial combi- torial properties of such structures and to exploit these properties in order to achieve superior performance for the corresponding computational problems. Over recent years a steady ?ow of high-quality research on this subject has changed a sparse set of isolated results into a fully-?edged area of algorithmics.

Zielgruppe

Research

Autoren/Hrsg.

Giancarlo, Raffaele

Sankoff, David

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Künstliche Intelligenz Mustererkennung, Biometrik
• Mathematik | Informatik Mathematik Algebra Elementare Algebra
• Mathematik | Informatik EDV | Informatik Professionelle Anwendung Computer-Aided Design (CAD)
• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Datenkompression, Dokumentaustauschformate
• Mathematik | Informatik EDV | Informatik Angewandte Informatik Computeranwendungen in Wissenschaft & Technologie
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Grafikprogrammierung
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
• Technische Wissenschaften Technik Allgemein Computeranwendungen in der Technik

Inhaltsverzeichnis

Invited Lectures.- Identifying and Filtering Near-Duplicate Documents.- Machine Learning for Efficient Natural-Language Processing.- Browsing around a Digital Library: Today and Tomorrow.- Summer School Lectures.- Algorithmic Aspects of Speech Recognition: A Synopsis.- Some Results on Flexible-Pattern Discovery.- Contributed Papers.- Explaining and Controlling Ambiguity in Dynamic Programming.- A Dynamic Edit Distance Table.- Parametric Multiple Sequence Alignment and Phylogeny Construction.- Tsukuba BB: A Branch and Bound Algorithm for Local Multiple Sequence Alignment.- A Polynomial Time Approximation Scheme for the Closest Substring Problem.- Approximation Algorithms for Hamming Clustering Problems.- Approximating the Maximum Isomorphic Agreement Subtree Is Hard.- A Faster and Unifying Algorithm for Comparing Trees.- Incomplete Directed Perfect Phylogeny.- The Longest Common Subsequence Problem for Arc-Annotated Sequences.- Boyer—Moore String Matching over Ziv-Lempel Compressed Text.- A Boyer—Moore Type Algorithm for Compressed Pattern Matching.- Approximate String Matching over Ziv—Lempel Compressed Text.- Improving Static Compression Schemes by Alphabet Extension.- Genome Rearrangement by Reversals and Insertions/Deletions of Contiguous Segments.- A Lower Bound for the Breakpoint Phylogeny Problem.- Structural Properties and Tractability Results for Linear Synteny.- Shift Error Detection in Standardized Exams.- An Upper Bound for Number of Contacts in the HP-Model on the Face-Centered-Cubic Lattice (FCC).- The Combinatorial Partitioning Method.- Compact Suffix Array.- Linear Bidirectional On-Line Construction of Affix Trees.- Using Suffix Trees for Gapped Motif Discovery.- Indexing Text with Approximate q-Grams.- Simple Optimal String Matching Algorithm.-Exact and Efficient Computation of the Expected Number of Missing and Common Words in Random Texts.- Periods and Quasiperiods Characterization.- Finding Maximal Quasiperiodicities in Strings.- On the Complexity of Determining the Period of a String.