Ebook: Combinatorial Pattern Matching: 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings

This book constitutes the refereed proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, held in Bad Herrenalb (near Karlsruhe), Germany, in June 2013. The 21 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 51 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, 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 problem or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.

---

This book constitutes the refereed proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, held in Bad Herrenalb (near Karlsruhe), Germany, in June 2013. The 21 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 51 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, 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 problem or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.

---

This book constitutes the refereed proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, held in Bad Herrenalb (near Karlsruhe), Germany, in June 2013. The 21 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 51 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, 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 problem or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.
Content:
Front Matter....Pages -
Forty Years of Text Indexing....Pages 1-10
LCP Magic....Pages 11-11
Discrete Methods for Image Analysis Applied to Molecular Biology....Pages 12-12
Locating All Maximal Approximate Runs in a String....Pages 13-27
On Minimal and Maximal Suffixes of a Substring....Pages 28-37
Converting SLP to LZ78 in almost Linear Time....Pages 38-49
A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm....Pages 50-61
Compact q-Gram Profiling of Compressed Strings....Pages 62-73
A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform....Pages 74-82
Pattern Matching with Variables: A Multivariate Complexity Analysis....Pages 83-94
New Algorithms for Position Heaps....Pages 95-106
Document Listing on Repetitive Collections....Pages 107-119
Approximating Shortest Superstring Problem Using de Bruijn Graphs....Pages 120-129
Local Search for String Problems: Brute Force Is Essentially Optimal....Pages 130-141
Space-Efficient Construction Algorithm for the Circular Suffix Tree....Pages 142-152
Efficient Lyndon Factorization of Grammar Compressed Text....Pages 153-164
Approximation of Grammar-Based Compression via Recompression....Pages 165-176
Fast Algorithm for Partial Covers in Words....Pages 177-188
Linear Time Lempel-Ziv Factorization: Simple, Fast, Small....Pages 189-200
External Memory Generalized Suffix and LCP Arrays Construction....Pages 201-210
Efficient All Path Score Computations on Grid Graphs....Pages 211-222
Time-Space Trade-Offs for the Longest Common Substring Problem....Pages 223-234
A Succinct Grammar Compression....Pages 235-246
Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings....Pages 247-258
Back Matter....Pages -

---

This book constitutes the refereed proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, held in Bad Herrenalb (near Karlsruhe), Germany, in June 2013. The 21 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 51 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, 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 problem or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.
Content:
Front Matter....Pages -
Forty Years of Text Indexing....Pages 1-10
LCP Magic....Pages 11-11
Discrete Methods for Image Analysis Applied to Molecular Biology....Pages 12-12
Locating All Maximal Approximate Runs in a String....Pages 13-27
On Minimal and Maximal Suffixes of a Substring....Pages 28-37
Converting SLP to LZ78 in almost Linear Time....Pages 38-49
A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm....Pages 50-61
Compact q-Gram Profiling of Compressed Strings....Pages 62-73
A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform....Pages 74-82
Pattern Matching with Variables: A Multivariate Complexity Analysis....Pages 83-94
New Algorithms for Position Heaps....Pages 95-106
Document Listing on Repetitive Collections....Pages 107-119
Approximating Shortest Superstring Problem Using de Bruijn Graphs....Pages 120-129
Local Search for String Problems: Brute Force Is Essentially Optimal....Pages 130-141
Space-Efficient Construction Algorithm for the Circular Suffix Tree....Pages 142-152
Efficient Lyndon Factorization of Grammar Compressed Text....Pages 153-164
Approximation of Grammar-Based Compression via Recompression....Pages 165-176
Fast Algorithm for Partial Covers in Words....Pages 177-188
Linear Time Lempel-Ziv Factorization: Simple, Fast, Small....Pages 189-200
External Memory Generalized Suffix and LCP Arrays Construction....Pages 201-210
Efficient All Path Score Computations on Grid Graphs....Pages 211-222
Time-Space Trade-Offs for the Longest Common Substring Problem....Pages 223-234
A Succinct Grammar Compression....Pages 235-246
Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings....Pages 247-258
Back Matter....Pages -
....