Combinatorial Pattern Matching: 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings

Front Cover
Springer Science & Business Media, Jun 22, 2007 - Computers - 366 pages
0 Reviews
The papers contained in this volume were presented at the 18th Annual S- posium on Combinatorial Pattern Matching (CPM 2007) held at the University of Western Ontario, in London, Ontario, Canada from July 9 to 11, 2007. All the papers presented at the conference are original research contri- tions on computational pattern matching and analysis, data compression and compressed text processing, su?x arrays and trees, and computational biology. They were selected from 64 submissions. Each submission was reviewed by at least three reviewers. The committee decided to accept 32 papers. The p- gramme also included three invited talks by Tao Jiang from the University of California, Riverside, USA, S. Muthukrishnan from Rutgers University, USA, and Frances Yao from City University of Hong Kong, Hong Kong. Combinatorial Pattern Matching addresses issues of searching and matching stringsandmorecomplicatedpatternssuchastrees,regularexpressions,graphs, point sets, and arrays.The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed e?ciently.
 

What people are saying - Write a review

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

Contents

Beyond Sequence Similarity Search
1
Some Classic and Some Modern Problems
2
Algorithmic Problems in Scheduling Jobs on VariableSpeed Processors
3
Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
4
On Demand String Sorting over Unbounded Alphabets
16
Finding Witnesses by Peeling
28
CacheOblivious Index for Approximate String Matching
40
Improved Approximate String Matching and Regular Expression Matching on ZivLempel Compressed Texts
52
Fast Convolution in Sparse Data and Applications
183
Better Structure Comparisons by Using Domainknowledge
195
SpaceEfficient Algorithms for Document Retrieval
205
Compressed Text Indexes with Fast Locate
216
A Tractability Border
228
Approximation and Combinatorics
241
Identification of Distinguishing Motifs
253
Algorithms for Computing the Longest Parameterized Common Subsequence
265

Selfnormalised Distance with Dont Cares
63
MovetoFront Distance Coding and Inversion Frequencies Revisited
71
A LempelZiv Text Index on Secondary Storage
83
Dynamic RankSelect Structures with Applications to RunLength Encoded Texts Extended Abstract
95
Most BurrowsWheeler Based Compressors Are Not Optimal
107
Nonbreaking Similarity of Genomes with Gene Repetitions
119
A New and Faster Method of Sorting by Transpositions
131
Finding Compact Structural Motifs
142
Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants
150
Computing Exact pValue for Structured Motif
162
Improved Sketching of Hamming Distance with Error Correcting
173
FixedParameter Tractability of the Maximum Agreement Supertree Problem
274
TwoDimensional Range Minimum Queries
286
Tiling Periodicity
295
Fast and Practical Algorithms for Computing All the Runs in a String
307
Longest Common Separable Pattern Among Permutations
316
Suffix Arrays on Words
328
Efficient Computation of Substring Equivalence Classes with Suffix Arrays
340
A Simple Construction of TwoDimensional Suffix Trees in Linear Time
352
Author Index
365
Copyright

Other editions - View all

Common terms and phrases