StringologyTimes

CPM for Stringologist

CPM 2024

  1. Efficient Construction of Long Orientable Sequences.
  2. Solving the Minimal Positional Substring Cover Problem in Sublinear Space.
  3. A Class of Heuristics for Reducing the Number of BWT-Runs in the String Ordering Problem.
  4. Online Context-Free Recognition in OMv Time.
  5. A Data Structure for the Maximum-Sum Segment Problem with Offsets.
  6. Random Wheeler Automata.
  7. Algorithms for Galois Words: Detection, Factorization, and Rotation.
  8. Finding Diverse Strings and Longest Common Subsequences in a Graph.
  9. Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds.
  10. Faster Sliding Window String Indexing in Streams.
  11. Walking on Words.
  12. Exploiting New Properties of String Net Frequency for Efficient Computation.
  13. Connecting de Bruijn Graphs.
  14. Simplified Tight Bounds for Monotone Minimal Perfect Hashing.
  15. Searching 2D-Strings for Matching Frames.
  16. Minimizing the Minimizers via Alphabet Reordering.
  17. Front Matter, Table of Contents, Preface, Conference Organization.
  18. Internal Pattern Matching in Small Space and Applications.
  19. Closing the Gap: Minimum Space Optimal Time Distance Labeling Scheme for Interval Graphs.
  20. Shortest Cover After Edit.
  21. Hairpin Completion Distance Lower Bound.
  22. The Rational Construction of a Wheeler DFA.
  23. Computing the LCP Array of a Labeled Graph.
  24. Tight Bounds for Compressing Substring Samples.
  25. Maintaining the Size of LZ77 on Semi-Dynamic Strings.
  26. When Is the Normalized Edit Distance over Non-Uniform Weights a Metric?
  27. Reconstructing General Matching Graphs.
  28. BAT-LZ out of hell.
  29. Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space.

CPM 2023

  1. L-Systems for Measuring Repetitiveness.
  2. Optimal LZ-End Parsing Is Hard.
  3. Merging Sorted Lists of Similar Strings.
  4. Front Matter, Table of Contents, Preface, Conference Organization.
  5. Encoding Hard String Problems with Answer Set Programming.
  6. On the Impact of Morphisms on BWT-Runs.
  7. Optimal Near-Linear Space Heaviest Induced Ancestors.
  8. Approximation Algorithms for the Longest Run Subsequence Problem.
  9. Suffix-Prefix Queries on a Dictionary.
  10. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond.
  11. On Distances Between Words with Parameters.
  12. From Bit-Parallelism to Quantum String Matching for Labelled Graphs.
  13. Faster Prefix-Sorting Algorithms for Deterministic Finite Automata.
  14. Compressed Indexing for Consecutive Occurrences.
  15. MONI Can Find k-MEMs.
  16. Trie-Compressed Adaptive Set Intersection.
  17. Order-Preserving Squares in Strings.
  18. Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String.
  19. Improving the Sensitivity of MinHash Through Hash-Value Analysis.
  20. Sliding Window String Indexing in Streams.
  21. PalFM-Index: FM-Index for Palindrome Pattern Matching.
  22. On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem.
  23. MUL-Tree Pruning for Consistency and Compatibility.
  24. String Factorization via Prefix Free Families.
  25. Computing MEMs on Repetitive Text Collections.
  26. Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor.
  27. Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications.

CPM 2022

  1. Cartesian Tree Subsequence Matching.
  2. Indexable Elastic Founder Graphs of Minimum Height.
  3. Efficient Construction of the BWT for Repetitive Text Using String Compression.
  4. Longest Palindromic Substring in Sublinear Time.
  5. Permutation Pattern Matching for Doubly Partially Ordered Patterns.
  6. Rectangular Tile Covers of 2D-Strings.
  7. Arbitrary-Length Analogs to de Bruijn Sequences.
  8. Beyond the Longest Letter-Duplicated Subsequence Problem.
  9. Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants.
  10. The Dynamic k-Mismatch Problem.
  11. On Strings Having the Same Length- k Substrings.
  12. An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions.
  13. The Normalized Edit Distance with Uniform Operation Costs Is a Metric.
  14. Linear-Time Computation of Shortest Covers of All Rotations of a String.
  15. Bi-Directional r-Indexes.
  16. Partial Permutations Comparison, Maintenance and Applications.
  17. Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations.
  18. The Fine-Grained Complexity of Episode Matching.
  19. Back-To-Front Online Lyndon Forest Construction.
  20. Reduction Ratio of the IS-Algorithm: Worst and Random Cases.
  21. Invitation to Combinatorial Reconfiguration (Invited Talk).
  22. Making de Bruijn Graphs Eulerian.
  23. A Theoretical and Experimental Analysis of BWT Variants for String Collections.
  24. Mechanical Proving with Walnut for Squares and Cubes in Partial Words.
  25. Using Automata and a Decision Procedure to Prove Results in Pattern Matching (Invited Talk).
  26. Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-Isomorphic, 2D, etc. (Invited Talk).
  27. Reordering a Tree According to an Order on Its Leaves.
  28. Front Matter, Table of Contents, Preface, Conference Organization.
  29. Minimal Absent Words on Run-Length Encoded Strings.
  30. {RePair} Grammars Are the Smallest Grammars for Fibonacci Words.

CPM 2021

  1. On-Line Pattern Matching on D-Texts (Invited Talk).
  2. Internal Shortest Absent Word Queries.
  3. A Fast and Small Subsampled R-Index.
  4. Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time.
  5. A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs.
  6. An Invertible Transform for Efficient String Matching in Labeled Digraphs.
  7. AWLCO: All-Window Length Co-Occurrence.
  8. Front Matter, Table of Contents, Preface, Conference Organization.
  9. Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance.
  10. Compressed Weighted de Bruijn Graphs.
  11. Ranking Bracelets in Polynomial Time.
  12. Efficient Algorithms for Counting Gapped Palindromes.
  13. The k-Mappability Problem Revisited.
  14. Optimal Construction of Hierarchical Overlap Graphs.
  15. Repetitions in Strings: A “Constant” Problem (Invited Talk).
  16. Computing Edit Distance (Invited Talk).
  17. Gapped Indexing for Consecutive Occurrences.
  18. A Compact Index for Cartesian Tree Matching.
  19. Computing Covers of 2D-Strings.
  20. String Sanitization Under Edit Distance: Improved and Generalized.
  21. R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space.
  22. Constructing Strings Avoiding Forbidden Substrings.
  23. Disorders and Permutations.
  24. The Longest Run Subsequence Problem: Further Complexity Results.
  25. Data Structures for Categorical Path Counting Queries.
  26. Weighted Ancestors in Suffix Trees Revisited.

CPM 2020

  1. Faster Binary Mean Computation Under Dynamic Time Warping.
  2. Compressed Orthogonal Search on Suffix Arrays with Applications to Range LCP.
  3. Double String Tandem Repeats.
  4. On Two Measures of Distance Between Fully-Labelled Trees.
  5. Genomic Problems Involving Copy Number Profiles: Complexity and Algorithms.
  6. Counting Distinct Patterns in Internal Dictionary Matching.
  7. Front Matter, Table of Contents, Preface, Conference Organization.
  8. String Factorizations Under Various Collision Constraints.
  9. DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures.
  10. String Sanitization Under Edit Distance.
  11. Chaining with Overlaps Revisited.
  12. Parameterized Algorithms for Matrix Completion with Radius Constraints.
  13. Approximating Longest Common Substring with k mismatches: Theory and Practice.
  14. Unary Words Have the Smallest Levenshtein k-Neighbourhoods.
  15. Time-Space Tradeoffs for Finding a Long Common Substring.
  16. Approximating Text-To-Pattern Distance via Dimensionality Reduction.
  17. On Indeterminate Strings Matching.
  18. Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences.
  19. Finding the Anticover of a String.
  20. Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions.
  21. The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time.
  22. Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk).
  23. k-Approximate Quasiperiodicity under Hamming and Edit Distance.
  24. In-Place Bijective Burrows-Wheeler Transforms.
  25. FM-Index Reveals the Reverse Suffix Array.
  26. Efficient Tree-Structured Categorical Retrieval.
  27. Longest Common Subsequence on Weighted Sequences.
  28. Text Indexing and Searching in Sublinear Time.
  29. On Extensions of Maximal Repeats in Compressed Strings.
  30. Dynamic String Alignment.

CPM 2019

  1. Conversion from RLBWT to LZ77.
  2. Stringology Combats Microbiological Threats (Invited Talk).
  3. Cartesian Tree Matching and Indexing.
  4. Fully-Functional Bidirectional Burrows-Wheeler Indexes and Infinite-Order De Bruijn Graphs.
  5. Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform.
  6. On Maximal Repeats in Compressed Strings.
  7. Dichotomic Selection on Words: A Probabilistic Analysis.
  8. A New Class of Searchable and Provably Highly Compressible String Transformations.
  9. A Rearrangement Distance for Fully-Labelled Trees.
  10. Indexing the Bijective BWT.
  11. Streaming Dictionary Matching with Mismatches.
  12. Computing the Antiperiod(s) of a String.
  13. Hamming Distance Completeness.
  14. Searching Long Repeats in Streams.
  15. A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem.
  16. Some Variations on Lyndon Words (Invited Talk).
  17. Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding.
  18. Quasi-Linear-Time Algorithm for Longest Common Circular Factor.
  19. Computing Runs on a Trie.
  20. Front Matter, Table of Contents, Preface, Conference Organization.
  21. On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations.
  22. Simulating the DNA Overlap Graph in Succinct Space.
  23. Sufficient Conditions for Efficient Indexing Under Different Matchings.
  24. Faster Queries for Longest Substring Palindrome After Block Edit.
  25. Quasi-Periodicity in Streams.
  26. Finding a Small Number of Colourful Components.
  27. Compressed Multiple Pattern Matching.
  28. Online Algorithms for Constructing Linear-Size Suffix Trie.
  29. Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding.
  30. Approximating Approximate Pattern Matching.
  31. How to Exploit Periodicity (Invited Talk).
  32. Entropy Lower Bounds for Dictionary Compression.
  33. Optimal Rank and Select Queries on Dictionary-Compressed Text.

CPM 2018

  1. Can a permutation be sorted by best short swaps?.
  2. Lyndon Factorization of Grammar Compressed Texts Revisited.
  3. A Succinct Four Russians Speedup for Edit Distance Computation and One-against-many Banded Alignment.
  4. The Heaviest Induced Ancestors Problem Revisited.
  5. A Simple Linear-Time Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its Applications.
  6. Superstrings with multiplicities.
  7. Maximal Common Subsequence Algorithms.
  8. Online LZ77 Parsing and Matching Statistics with RLBWTs.
  9. Dualities in Tree Representations.
  10. Longest substring palindrome after edit.
  11. Longest Lyndon Substring After Edit.
  12. Linear-time algorithms for the subpath kernel.
  13. Fast Matching-based Approximations for Maximum Duo-Preservation String Mapping and its Weighted Variant.
  14. Front Matter, Table of Contents, Preface, Conference Organization.
  15. Slowing Down Top Trees for Better Worst-Case Compression.
  16. Non-Overlapping Indexing - Cache Obliviously.
  17. Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.
  18. On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure.
  19. Faster Online Elastic Degenerate String Matching.
  20. Quasi-Periodicity Under Mismatch Errors.
  21. Linear-Time Algorithm for Long LCF with k Mismatches.
  22. On Undetected Redundancy in the Burrows-Wheeler Transform.
  23. Nearest constrained circular words.
  24. Computing longest common square subsequences.
  25. Order-Preserving Pattern Matching Indeterminate Strings.

CPM 2017

  1. Longest Common Extensions with Recompression.
  2. A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem.
  3. Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings.
  4. Dynamic Elias-Fano Representation.
  5. Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers.
  6. Computing All Distinct Squares in Linear Time for Integer Alphabets.
  7. Document Listing on Repetitive Collections with Guaranteed Performance.
  8. Beyond Adjacency Maximization: Scaffold Filling for New String Distances.
  9. Communication and Streaming Complexity of Approximate Pattern Matching.
  10. On-Line Pattern Matching on Similar Texts.
  11. On the Weighted Quartet Consensus Problem.
  12. Approximate Cover of Strings.
  13. Palindromic Length in Linear Time.
  14. Tight Bounds on the Maximum Number of Shortest Unique Substrings.
  15. Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars.
  16. Position Heaps for Parameterized Strings.
  17. The Longest Filled Common Subsequence Problem.
  18. Wheeler Graphs: Variations on a Theme by Burrows and Wheeler.
  19. Lempel-Ziv Compression in a Sliding Window.
  20. Gapped Pattern Statistics.
  21. Representing the Suffix Tree with the CDAWG.
  22. Deterministic Indexing for Packed Strings.
  23. Shortest Superstring.
  24. Faster STR-IC-LCS Computation via RLE.
  25. Can We Recover the Cover?.
  26. Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping.
  27. From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back.
  28. Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing.
  29. Recompression of SLPs.
  30. Optimal Omnitig Listing for Safe and Complete Contig Assembly.
  31. Path Queries on Functions.
  32. Synergistic Solutions on MultiSets.

CPM 2016

  1. Hardness of RNA Folding Problem With Four Symbols.
  2. Linear-time Suffix Sorting - A New Approach for Suffix Array Construction.
  3. Space-Efficient Dictionaries for Parameterized and Order-Preserving Pattern Matching.
  4. Finding Maximal 2-Dimensional Palindromes.
  5. On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching.
  6. Factorizing a String into Squares in Linear Time.
  7. Efficient Index for Weighted Sequences.
  8. On Almost Monge All Scores Matrices.
  9. Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction.
  10. Genomic Scaffold Filling Revisited.
  11. Faster Longest Common Extension Queries in Strings over General Alphabets.
  12. A Linear-Time Algorithm for the Copy Number Transformation Problem.
  13. A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem.
  14. Color-Distance Oracles and Snippets.
  15. Minimal Suffix and Rotation of a Substring in Optimal Time.
  16. Boxed Permutation Pattern Matching.
  17. Estimating Statistics on Words Using Ambiguous Descriptions.
  18. Front Matter, Table of Contents, Preface.
  19. Succinct Online Dictionary Matching with Improved Worst-Case Guarantees.
  20. Efficient Non-Binary Gene Tree Resolution with Weighted Reconciliation Cost.
  21. Fully-online Construction of Suffix Trees for Multiple Texts.
  22. Graph Motif Problems Parameterized by Dual.
  23. Reconstruction of Trees from Jumbled and Weighted Subtrees.
  24. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
  25. Fast Compatibility Testing for Rooted Phylogenetic Trees.
  26. Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.
  27. The Nearest Colored Node in a Tree.
  28. Optimal Prefix Free Codes with Partial Sorting.
  29. Encoding Two-Dimensional Range Top-k Queries.
  30. Longest Common Substring with Approximately k Mismatches.

CPM 2015

  1. Lempel Ziv Computation in Small Space (LZ-CISS).
  2. Succinct Non-overlapping Indexing.
  3. Combinatorial RNA Design: Designability and Structure-Approximating Algorithm.
  4. Dictionary Matching with Uneven Gaps.
  5. A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm.
  6. Sorting by Cuts, Joins and Whole Chromosome Duplications.
  7. Tighter Bounds for the Sum of Irreducible LCP Values.
  8. Longest Common Extensions in Trees.
  9. Longest Common Extensions in Sublinear Space.
  10. LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding.
  11. Encoding Nearest Larger Values.
  12. Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints.
  13. The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets.
  14. Composite Repetition-Aware Data Structures.
  15. On the Readability of Overlap Digraphs.
  16. Online Detection of Repetitions with Backtracking.
  17. Alphabet-Dependent String Searching with Wexponential Search Trees.
  18. On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem.
  19. Parameterized Complexity of Superstring Problems.
  20. Compact Indexes for Flexible Top- k k Retrieval.
  21. Encodings of Range Maximum-Sum Segment Queries and Applications.
  22. Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process.
  23. On Maximal Unbordered Factors.
  24. Parallel External Memory Suffix Sorting.
  25. On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling.
  26. Greedy Conjecture for Strings of Length 4.
  27. Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree.
  28. A Framework for Space-Efficient String Kernels.
  29. Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem.
  30. Ranked Document Retrieval with Forbidden Pattern.
  31. Range Minimum Query Indexes in Higher Dimensions.
  32. Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis.
  33. String Powers in Trees.
  34. Fast String Dictionary Lookup with One Error.

CPM 2014

  1. On the Efficiency of the Hamming C-Centerstring Problems.
  2. Searching of Gapped Repeats and Subrepetitions in a Word.
  3. Shortest Unique Substring Query Revisited.
  4. Indexed Geometric Jumbled Pattern Matching.
  5. On the DCJ Median Problem.
  6. Parameterized Complexity Analysis for the Closest String with Wildcards Problem.
  7. String Range Matching.
  8. Computing Palindromic Factorizations and Palindromic Covers On-line.
  9. Dictionary Matching with One Gap.
  10. An Improved Query Time for Succinct Dynamic Dictionary Matching.
  11. A really Simple Approximation of Smallest Grammar.
  12. Most Recent Match Queries in On-Line Suffix Trees.
  13. Permuted Scaled Matching.
  14. Computing Minimal and Maximal Suffixes of a Substring Revisited.
  15. From Indexing Data Structures to de Bruijn Graphs.
  16. On Hardness of Several String Indexing Problems.
  17. On Combinatorial Generation of Prefix Normal Words.
  18. Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence.
  19. Randomized and Parameterized Algorithms for the Closest String Problem.
  20. The Worst Case Complexity of Maximum Parsimony.
  21. Approximate String Matching Using a Bidirectional Index.
  22. Efficient Algorithms for Shortest Partial Seeds in Words.
  23. Approximate On-line Palindrome Recognition, and Applications.
  24. Order-Preserving Pattern Matching with k Mismatches.
  25. Compactness-Preserving Mapping on Trees.
  26. Reversal Distances for Strings with Few Blocks or Small Alphabets.
  27. Compressed Subsequence Matching and Packed Tree Coloring.
  28. Encodings for Range Majority Queries.

CPM 2013

  1. Pattern Matching with Variables: A Multivariate Complexity Analysis.
  2. A Constant-Space Comparison-Based Algorithm for Computing the Burrows-Wheeler Transform.
  3. Approximation of Grammar-Based Compression via Recompression.
  4. Discrete Methods for Image Analysis Applied to Molecular Biology.
  5. Fast Algorithm for Partial Covers in Words.
  6. A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm.
  7. Efficient Lyndon Factorization of Grammar Compressed Text.
  8. Locating All Maximal Approximate Runs in a String.
  9. Compact q-Gram Profiling of Compressed Strings.
  10. New Algorithms for Position Heaps.
  11. External Memory Generalized Suffix and LCP Arrays Construction.
  12. On Minimal and Maximal Suffixes of a Substring.
  13. Efficient All Path Score Computations on Grid Graphs.
  14. A Succinct Grammar Compression.
  15. Approximating Shortest Superstring Problem Using de Bruijn Graphs.
  16. Linear Time Lempel-Ziv Factorization: Simple, Fast, Small.
  17. Converting SLP to LZ78 in almost Linear Time.
  18. Space-Efficient Construction Algorithm for the Circular Suffix Tree.
  19. Forty Years of Text Indexing.
  20. Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings.
  21. Local Search for String Problems: Brute Force Is Essentially Optimal.
  22. Document Listing on Repetitive Collections.
  23. LCP Magic.
  24. Time-Space Trade-Offs for the Longest Common Substring Problem.

CPM 2012

  1. A Linear Kernel for the Complementary Maximal Strip Recovery Problem.
  2. Efficient Algorithm for Circular Burrows-Wheeler Transform.
  3. An Efficient Linear Pseudo-minimization Algorithm for Aho-Corasick Automata.
  4. Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees.
  5. Computing the Rooted Triplet Distance between Galled Trees by Counting Triangles.
  6. Local Exact Pattern Matching for Non-fixed RNA Structures.
  7. Partitioning into Colorful Components by Minimum Edge Deletions.
  8. The Parameterized Complexity of the Shared Center Problem.
  9. Document Listing for Queries with Excluded Pattern.
  10. Compressed String Dictionary Look-Up with Edit Distance One.
  11. Cross-Document Pattern Matching.
  12. Faster and Simpler Minimal Conflicting Set Identification - (Extended Abstract).
  13. FEMTO: Fast Search of Large Sequence Collections.
  14. On the Closest String via Rank Distance.
  15. Wavelet Trees for All.
  16. Finding Longest Common Segments in Protein Structures in Nearly Linear Time.
  17. Gene Regulation, Protein Networks and Disease: A Computational Perspective.
  18. Time-Space Trade-Offs for Longest Common Extensions.
  19. Simple and Efficient LZW-Compressed Multiple Pattern Matching.
  20. Constant-Time Word-Size String Matching.
  21. Impact of the Energy Model on the Complexity of RNA Folding with Pseudoknots.
  22. Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval.
  23. Approximation Algorithms and Hardness Results for Shortest Path Based Graph Orientations.
  24. Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence.
  25. Least Random Suffix/Prefix Matches in Output-Sensitive Time.
  26. The Maximum Number of Squares in a Tree.
  27. Speeding Up q-Gram Mining on Grammar-Based Compressed Texts.
  28. Minimum Leaf Removal for Reconciliation: Complexity and Algorithms.
  29. Efficient Two-Dimensional Pattern Matching with Scaling and Rotation and Higher-Order Interpolation.
  30. Pattern Matching in Multiple Streams.
  31. The Complexity of String Partitioning.
  32. Fixed-Parameter Algorithms for Finding Agreement Supertrees.
  33. On Approximating String Selection Problems with Outliers.
  34. Computing the Burrows-Wheeler Transform of a String and Its Reverse.
  35. Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths.

CPM 2011

  1. Computational Regulatory Genomics.
  2. Self-indexing Based on LZ77.
  3. Sparse and Truncated Suffix Trees on Variable-Length Codes.
  4. Succincter Text Indexing with Wildcards.
  5. Counting Colours in Compressed Strings.
  6. Real-Time Streaming String-Matching.
  7. Phylogenetic Footprinting and Consistent Sets of Local Aligments.
  8. Fast Error-Tolerant Quartet Phylogeny Algorithms.
  9. Forest Alignment with Affine Gaps and Anchors.
  10. Approximation Algorithms for Orienting Mixed Graphs.
  11. Quick Greedy Computation for Minimum Common String Partitions.
  12. Polynomial-Time Approximation Algorithms for Weighted LCS Problem.
  13. Palindrome Pattern Matching.
  14. Tractability Results for the Consecutive-Ones Property with Multiplicity.
  15. Automatic Discovery of Patterns in Media Content.
  16. Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts.
  17. Finding Approximate and Constrained Motifs in Graphs.
  18. On the Weak Prefix-Search Problem.
  19. Tractability and Approximability of Maximal Strip Recovery.
  20. Edit Distance with Duplications and Contractions Revisited.
  21. Algorithms on Grammar-Compressed Strings.
  22. Restricted Common Superstring and Restricted Common Supersequence.
  23. String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time.
  24. Lempel-Ziv Factorization Revisited.
  25. Substring Range Reporting.
  26. Unique Perfect Phylogeny Is NP-Hard.
  27. Efficient Seeds Computation Revisited.
  28. A d-Step Approach for Distinct Squares in Strings.
  29. Lightweight BWT Construction for Very Large String Collections.
  30. Simple Real-Time Constant-Space String Matching.
  31. On Wavelet Tree Construction.
  32. Frequent Submap Discovery.
  33. A Combinatorial Model of Phyllotaxis Perturbations in Arabidopsis thaliana.
  34. Space Lower Bounds for Online Pattern Matching.
  35. LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations.
  36. A Coarse-to-Fine Approach to Computing the k-Best Viterbi Paths.
  37. Efficient Matching of Biological Sequences Allowing for Non-overlapping Inversions.
  38. Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees.
  39. Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies.

CPM 2010

  1. Cover Array String Reconstruction.
  2. On the Parameterized Complexity of Some Optimization Problems Related to Multiple-Interval Graphs.
  3. Sampled Longest Common Prefix Array.
  4. Affine Image Matching Is Uniform TC0-Complete.
  5. Compression, Indexing, and Retrieval for Massive String Data.
  6. The Property Suffix Tree with Dynamic Properties.
  7. Breakpoint Distance and PQ-Trees.
  8. Approximate All-Pairs Suffix/Prefix Overlaps.
  9. Verifying a Parameterized Border Array in O(n1.5) Time.
  10. Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks.
  11. Implicit Hitting Set Problems and Multi-genome Alignment.
  12. A Compact Representation of Nondeterministic (Suffix) Automata for the Bit-Parallel Approach.
  13. Mod/Resc Parsimony Inference.
  14. Old and New in Stringology.
  15. Extended Islands of Tractability for Parsimony Haplotyping.
  16. Small-Space 2D Compressed Dictionary Matching.
  17. Algorithms for Three Versions of the Shortest Common Superstring Problem.
  18. Succinct Dictionary Matching with No Slowdown.
  19. Succinct Representations of Separable Graphs.
  20. Parallel and Distributed Compressed Indexes.
  21. A Minimal Periods Algorithm with Applications.
  22. Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
  23. Optimizing Restriction Site Placement for Synthetic Genomes.
  24. Bounds on the Minimum Mosaic of Population Sequences under Recombination.
  25. Extension and Faster Implementation of the GRP Transform for Lossless Compression.
  26. Finding Optimal Alignment and Consensus of Circular Strings.
  27. Bidirectional Search in a String with Wavelet Trees.
  28. The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection.
  29. Building the Minimal Automaton of A*X in Linear Time, When X Is of Bounded Cardinality.
  30. Algorithms for Forest Pattern Matching.
  31. Pseudo-realtime Pattern Matching: Closing the Gap.

CPM 2009

  1. Haplotype Inference Constrained by Plausible Haplotype Data.
  2. Reoptimization of the Shortest Common Superstring Problem.
  3. Permuted Longest-Common-Prefix Array.
  4. Finding All Sorting Tandem Duplication Random Loss Operations.
  5. Linear Time Suffix Array Construction Using D-Critical Substrings.
  6. New Complexity Bounds for Image Matching under Rotation and Scaling.
  7. Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard.
  8. Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure.
  9. An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings.
  10. Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time.
  11. Periodic String Comparison.
  12. On the Value of Multiple Read/Write Streams for Data Compression.
  13. Fast RNA Structure Alignment for Crossing Input Structures.
  14. CPM’s 20th Anniversary: A Statistical Retrospective.
  15. Modeling and Algorithmic Challenges in Online Social Networks.
  16. Graph Mining: Patterns, Generators and Tools.
  17. Online Approximate Matching with Non-local Distances.
  18. LCS Approximation via Embedding into Local Non-repetitive Strings.
  19. Maximum Motif Problem in Vertex-Colored Graphs.
  20. Fast Searching in Packed Strings.
  21. Generalized Substring Compression.
  22. Statistical Properties of Factor Oracles.
  23. Average-Case Analysis of Perfect Sorting by Reversals.
  24. Deconstructing Intractability: A Case Study for Interval Constrained Coloring.
  25. Quasi-distinct Parsing and Optimal Compression Methods.
  26. Multiple Alignment of Biological Networks: A Flexible Approach.
  27. Text Indexing, Suffix Sorting, and Data Compression: Common Problems and Techniques.
  28. Sparse RNA Folding: Time and Space Efficient Algorithms.
  29. Faster and Space-Optimal Edit Distance “1” Dictionary.
  30. The Structure of Level-k Phylogenetic Networks.
  31. Efficient Inference of Haplotypes from Genotypes on a Pedigree with Mutations and Missing Alleles (Extented Abstract).

CPM 2008

  1. Faster Algorithm for the Set Variant of the String Barcoding Problem.
  2. An Improved Succinct Representation for Dynamic k-ary Trees.
  3. A Black Box for Online Approximate Pattern Matching.
  4. Matching Integer Intervals by Minimal Sets of Binary Words with don’t cares.
  5. Finding Additive Biclusters with Random Background.
  6. Approximate String Matching with Address Bit Errors.
  7. Dynamic Fully-Compressed Suffix Trees.
  8. Why Greed Works for Shortest Common Superstring Problem.
  9. On the Longest Common Parameterized Subsequence.
  10. Constrained LCS: Hardness and Approximation.
  11. Computing Inverse ST in Linear Complexity.
  12. Fast Algorithms for Computing Tree LCS.
  13. HP Distance Via Double Cut and Join Distance.
  14. A Linear Delay Algorithm for Building Concept Lattices.
  15. Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics.
  16. An(other) Entropy-Bounded Compressed Suffix Tree.
  17. Lower Bounds for Succinct Data Structures.
  18. Analysis of the Size of Antidictionary in.
  19. Two-Dimensional Pattern Matching with Combined Scaling and Rotation.
  20. Parameterized Algorithms and Hardness Results for Some Graph Motif Problems.
  21. The Changing Face of Web Search.
  22. Towards a Solution to the “Runs” Conjecture.
  23. Fixed Parameter Tractable Alignment of RNA Structures Including Arbitrary Pseudoknots.
  24. On Compact Representations of All-Pairs-Shortest-Path-Distance Matrices.
  25. On-Line Approximate String Matching with Bounded Errors.
  26. Searching for Gapped Palindromes.
  27. Finding Largest Well-Predicted Subset of Protein Structure Models.
  28. ReCombinatorics: Combinatorial Algorithms for Studying the History of Recombination in Populations.

CPM 2007

  1. Longest Common Separable Pattern Among Permutations.
  2. Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications.
  3. Space-Efficient Algorithms for Document Retrieval.
  4. Most Burrows-Wheeler Based Compressors Are Not Optimal.
  5. Self-normalised Distance with Don’t Cares.
  6. Processing Compressed Texts: A Tractability Border.
  7. Computing Exact p-Value for Structured Motif.
  8. Algorithmic Problems in Scheduling Jobs on Variable-Speed Processors.
  9. Common Structured Patterns in Linear Graphs: Approximation and Combinatorics.
  10. Move-to-Front, Distance Coding, and Inversion Frequencies Revisited.
  11. On Demand String Sorting over Unbounded Alphabets.
  12. Improved Sketching of Hamming Distance with Error Correcting.
  13. Suffix Arrays on Words.
  14. Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem.
  15. A New and Faster Method of Sorting by Transpositions.
  16. Finding Compact Structural Motifs.
  17. Fast and Practical Algorithms for Computing All the Runs in a String.
  18. Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants.
  19. Stringology: Some Classic and Some Modern Problems.
  20. Non-breaking Similarity of Genomes with Gene Repetitions.
  21. Identification of Distinguishing Motifs.
  22. Guided Forest Edit Distance: Better Structure Comparisons by Using Domain-knowledge.
  23. Cache-Oblivious Index for Approximate String Matching.
  24. Compressed Text Indexes with Fast Locate.
  25. Two-Dimensional Range Minimum Queries.
  26. A Simple Construction of Two-Dimensional Suffix Trees in Linear Time.
  27. Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts.
  28. Finding Witnesses by Peeling.
  29. Tiling Periodicity.
  30. Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions.
  31. Algorithms for Computing the Longest Parameterized Common Subsequence.
  32. Efficient Computation of Substring Equivalence Classes with Suffix Arrays.
  33. A Combinatorial Approach to Genome-Wide Ortholog Assignment: Beyond Sequence Similarity Search.
  34. A Lempel-Ziv Text Index on Secondary Storage.
  35. Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts.

CPM 2006

  1. Faster Two Dimensional Scaled Matching.
  2. Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs.
  3. Sublinear Algorithms for Parameterized Matching.
  4. Reducing the Space Requirement of LZ-Index.
  5. Local Alignment of RNA Sequences with Arbitrary Scoring Schemes.
  6. New Algorithms for Text Fingerprinting.
  7. Statistical Encoding of Succinct Data Structures.
  8. Obtaining Provably Good Performance from Suffix Trees in Secondary Storage.
  9. Property Matching and Weighted Matching.
  10. On-Line Linear-Time Construction of Word Suffix Trees.
  11. Algorithms for Finding a Most Similar Subforest.
  12. Common Substrings in Random Strings.
  13. Asynchronous Pattern Matching.
  14. A Linear Size Index for Approximate Pattern Matching.
  15. Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE.
  16. An Improved Algorithm for the Macro-evolutionary Phylogeny Problem.
  17. On the Repeat-Annotated Phylogenetic Tree Reconstruction Problem.
  18. A Compact Mathematical Programming Formulation for DNA Motif Finding.
  19. Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees.
  20. Faster Algorithms for Computing Longest Common Increasing Subsequences.
  21. Tiling an Interval of the Discrete Line.
  22. Dynamic Entropy-Compressed Sequences and Full-Text Indexes.
  23. Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents.
  24. Approximation of RNA Multiple Structural Alignment.
  25. Subsequence Combinatorics and Applications to Microarray Production, DNA Sequencing and Chaining Algorithms.
  26. New Bounds for Motif Finding in Strong Instances.
  27. Finding Common RNA Pseudoknot Structures in Polynomial Time.
  28. Large Scale Matching for Position Weight Matrices.
  29. Approximate Matching in Weighted Sequences.
  30. Fingerprint Clustering with Bounded Number of Missing Values.
  31. A Simpler Analysis of Burrows-Wheeler Based Compression.
  32. Identifying Co-referential Names Across Large Corpora.
  33. An O(n3/2sqrt(log n)) Algorithm for Sorting by Reciprocal Translocations.
  34. SNP and Haplotype Analysis - Algorithms and Applications.
  35. Geometric Suffix Tree: A New Index Structure for Protein 3-D Structures.
  36. Efficient Algorithms for Regular Expression Constrained Sequence Alignment.

CPM 2005

  1. Identifying Similar Surface Patches on Proteins Using a Spin-Image Surface Representation.
  2. Hardness of Optimal Spaced Seed Design.
  3. On the Complexity of Sparse Exon Assembly.
  4. Text Indexing with Errors.
  5. A Linear Tree Edit Distance Algorithm for Similar Ordered Trees.
  6. Regular Expression Constrained Sequence Alignment.
  7. Approximate Matching in the L1 Metric.
  8. Construction of Aho Corasick Automaton in Linear Time for Integer Alphabets.
  9. A Polynomial Time Matching Algorithm of Ordered Tree Patterns Having Height-Constrained Variables.
  10. Prefix-Free Regular-Expression Matching.
  11. Two Dimensional Parameterized Matching.
  12. Parametric Analysis for Ungapped Markov Models of Evolution.
  13. Linear Programming for Phylogenetic Reconstruction Based on Gene Rearrangements.
  14. A Fast Algorithm for Approximate String Matching on Gene Sequences.
  15. Mass Spectra Alignments and Their Significance.
  16. Weighted Directed Word Graph.
  17. Exact and Approximation Algorithms for DNA Tag Set Design.
  18. Incremental Inference of Relational Motifs with a Degenerate Alphabet.
  19. An Upper Bound on the Hardness of Exact Matrix Based Motif Discovery.
  20. Assessing the Significance of Sets of Words.
  21. Succinct Suffix Arrays Based on Run-Length Encoding.
  22. A New Periodicity Lemma.
  23. Sharper Upper and Lower Bounds for an Approximation Scheme for Consensus-Pattern.
  24. DNA Compression Challenge Revisited: A Dynamic Programming Approach.
  25. Inferring a Graph from Path Frequency.
  26. The Median Problem for the Reversal Distance in Circular Bacterial Genomes.
  27. Using PQ Trees for Comparative Genomics.
  28. A Simple Fast Hybrid Pattern-Matching Algorithm.
  29. An Extension of the Burrows Wheeler Transform and Applications to Sequence Comparison and Data Compression.
  30. Linear-Time Construction of Compressed Suffix Arrays Using o(n log n)-Bit Working Space for Large Alphabets.
  31. A New Compressed Suffix Tree Supporting Fast Search and Its Construction Algorithm Using Optimal Working Space.
  32. An Efficient Algorithm for Generating Super Condensed Neighborhoods.
  33. Faster Algorithms for delta, gamma-Matching and Related Problems.
  34. On the Longest Common Rigid Subsequence Problem.
  35. Reducing the Size of NFAs by Using Equivalences and Preorders.
  36. Speeding up Parsing of Biological Context-Free Grammars.
  37. An Optimal Algorithm for Online Square Detection.

CPM 2004

  1. Improved Single and Multiple Approximate String Matching.
  2. Average-Case Analysis of Approximate Trie Search (Extended Abstract).
  3. Compressed Compact Suffix Arrays.
  4. A Trie-Based Approach for Compacting Automata.
  5. Two Algorithms for LCS Consecutive Suffix Alignment.
  6. A Fast Set Intersection Algorithm for Sorted Sequences.
  7. Faster Two Dimensional Pattern Matching with Rotations.
  8. A Simple Optimal Representation for Balanced Parentheses.
  9. On the Average Sequence Complexity.
  10. New Results for the 2-Interval Pattern Problem.
  11. Computational Problems in Perfect Phylogeny Haplotyping: Xor-Genotypes and Tag SNPs.
  12. Sorting by Reversals in Subquadratic Time.
  13. Real-Time String Matching in Sublinear Space.
  14. Compressed Index for a Dynamic Collection of Texts.
  15. Sparse Normalized Local Alignment.
  16. Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem.
  17. A Linear-Time Algorithm for Computing Translocation Distance between Signed Genomes.
  18. Approximate Point Set Pattern Matching on Sequences and Planes.
  19. Optimizing Multiple Spaced Seeds for Homology Search.
  20. Multi-seed Lossless Filtration (Extended Abstract).
  21. Approximate Labelled Subtree Homeomorphism.
  22. Approximate String Matching Using Compressed Suffix Arrays.
  23. Computational Design of New and Recombinant Selenoproteins.
  24. Performing Local Similarity Searches with Variable Length Seeds.
  25. Finding Biclusters by Random Projections.
  26. Maximum Agreement and Compatible Supertrees (Extended Abstract).
  27. Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences.
  28. Reversal Distance without Hurdles and Fortresses.
  29. Sorting by Length-Weighted Reversals: Dealing with Signs and Circularity.
  30. Maximal Common Connected Sets of Interval Graphs.
  31. A Computational Model for RNA Multiple Structural Alignment..
  32. On the k-Closest Substring and k-Consensus Pattern Problems.
  33. The Protein Sequence Design Problem in Canonical Model on 2D and 3D Lattices.
  34. Efficient Algorithms for Finding Submasses in Weighted Strings.
  35. A Combinatorial Shape Matching Algorithm for Rigid Protein Docking.
  36. Small Phylogeny Problem: Character Evolution Trees.

CPM 2003

  1. Tuning String Matching for Huge Pattern Sets.
  2. Working on the Problem of Sorting by Transpositions on Genome Rearrangements.
  3. Multiple Genome Alignment: Chaining Algorithms Revisited.
  4. Haplotype Inference by Pure Parsimony.
  5. A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression.
  6. Sparse LCS Common Substring Alignment.
  7. An Exact and Polynomial Distance-Based Algorithm to Reconstruct Single Copy Tandem Duplication Trees.
  8. Constrained Tree Inclusion.
  9. Linear-Time Construction of Suffix Arrays.
  10. An Improved Algorithm for Generalized Comparison of Minisatellites.
  11. Optimal Partitions of Strings: A New Class of Burrows-Wheeler Compression Algorithms.
  12. Efficient Selection of Unique and Popular Oligos for Large EST Databases.
  13. Analysis of Tree Edit Distance Algorithms.
  14. A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions.
  15. Pattern Discovery in RNA Secondary Structure Using Affix Trees.
  16. Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals.
  17. On Minimizing Pattern Splitting in Multi-track String Matching.
  18. Two-Dimensional Pattern Matching with Rotations.
  19. Extracting Approximate Patterns.
  20. Alignment between Two Multiple Alignments.
  21. An Effective Algorithm for the Peptide De Novo Sequencing from MS/MS Spectrum.
  22. Average-Optimal Multiple Approximate String Matching.
  23. Optimal Spaced Seeds for Hidden Markov Models, with Application to Homologous Coding Regions.
  24. Fast Lightweight Suffix Array Construction and Checking.
  25. Space Efficient Linear Time Construction of Suffix Arrays.
  26. Distributed and Paged Suffix Trees for Large Genetic Databases.
  27. Complexities of the Centre and Median String Problems.
  28. More Efficient Left-to-Right Pattern Matching in Non-sequential Equational Programs.

CPM 2002

  1. A Better Method for Length Distribution Modeling in HMMs and Its Application to Gene Finding.
  2. Application of Lempel-Ziv Factorization to the Approximation of Grammar-Based Compression.
  3. Three Heuristics for delta-Matching: delta-BM Algorithms.
  4. Pattern Matching Problems over 2-Interval Sets.
  5. Identifying Occurrences of Maximal Pairs in Multiple Strings.
  6. Efficient Text Mining with Optimized Pattern Discovery.
  7. Towards Optimally Solving the LONGEST COMMON SUBSEQUENCE Problem for Sequences with Nested Arc Annotations in Linear Time.
  8. On the Complexity of Deriving Position Specific Score Matrices from Examples.
  9. Local Similarity Based Point-Pattern Matching.
  10. Faster Bit-Parallel Approximate String Matching.
  11. Simple and Practical Sequence Nearest Neighbors with Block Operations.
  12. Constructing NFA s by Optimal Use of Positions in Regular Expressions.
  13. Edit Distance with Move Operations.
  14. One-Gapped q-Gram Filtersfor Levenshtein Distance.
  15. Space-Economical Algorithms for Finding Maximal Unique Matches.
  16. The Problem of Context Sensitive String Matching.
  17. Block Merging for Off-Line Compression.
  18. The Minimum DAWG for All Suffixes of a String and Its Applications.
  19. String Matching with Stopper Encoding and Code Splitting.
  20. Two-Pattern Strings.
  21. Practical Software for Aligning ESTs to Human Genome.
  22. Optimal Exact and Fast Approximate Two Dimensional Pattern Matching Allowing Rotations.
  23. Statistical Identification of Uniformly Mutated Segments within Repeats.

CPM 2001

  1. An Output-Sensitive Flexible Pattern Discovery Algorithm.
  2. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications.
  3. On-Line Construction of Compact Directed Acyclic Word Graphs.
  4. Efficient Discovery of Proximity Patterns with Suffix Arrays.
  5. Finding All Common Intervals of k Permutations.
  6. A Very Elementary Presentation of the Hannenhalli-Pevzner Theory.
  7. Tandem Cyclic Alignment.
  8. An Extension of the Periodicity Lemma to Longer Periods (Invited Lecture).
  9. String Resemblance Systems: A Unifying Framework for String Similarity with Applications to Literature and Music.
  10. Episode Matching.
  11. Fuzzy Hamming Distance: A New Dissimilarity Measure.
  12. Computing the Equation Automaton of a Regular Expression in Space and Time.
  13. Generalized Pattern Matching and the Complexity of Unavoidability Testing.
  14. Efficient Experimental String Matching by Weak Factor Recognition.
  15. Regular Expression Searching over Ziv-Lempel Compressed Text.
  16. Multiple Pattern Matching Algorithms on Collage System.
  17. A Fast Algorithm for Optimal Alignment between Similar Ordered Trees.
  18. Balanced Suffix Trees (Invited Lecture).
  19. Better Filtering with Gapped q-Grams.
  20. What to Do with All this Hardware? (Invited Lecture).
  21. Approximate Matching of Run-Length Compressed Strings.
  22. Optimally Compact Finite Sphere Packings - Hydrophobic Cores in the FCC.
  23. Minimum Quartet Inconsistency Is Fixed Parameter Tractable.
  24. Parallel Lempel Ziv Coding.

CPM 2000

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

CPM 1999

  1. On the Complexity of Positional Sequencing by Hybridization.
  2. Computing Similarity between RNA Structures.
  3. The Compression of Subsegments of Images Described by Finite Automata.
  4. Finding Common Subsequences with Arcs and Pseudoknots.
  5. GESTALT: Genomic Steiner Alignments.
  6. Shift-And Approach to Pattern Matching in LZW Compressed Text.
  7. Hybridization and Genome Rearrangement.
  8. A Dynamic Data Structure for Reverse Lexicographically Sorted Prefixes.
  9. A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text.
  10. Finding Common RNA Secondary Structures from RNA Sequences.
  11. Bounds on the Number of String Subsequences.
  12. On the Structure of Syntenic Distance.
  13. Approximate Periods of Strings.
  14. Pattern Matching in Text Compressed by Using Antidictionaries.
  15. A New Indexing Method for Approximate String Matching.
  16. Applying an Edit Distance to the Matching of Tree Ring Sequences in Dendrochronology.
  17. Matching of Spots in 2D Electrophoresis Images. Point Matching Under Non-uniform Distortions.
  18. Physical Mapping with Repeated Probes: The Hypergraph Superstring Problem.
  19. Fast Multi-dimensional Approximate Pattern Matching.
  20. Ziv Lempel Compression of Huge Natural Language Data Tries Using Suffix Arrays.
  21. Finding Maximal Pairs with Bounded Gap.

CPM 1998

  1. Efficient Special Cases of Pattern Matching with Swaps.
  2. Constructing Suffix Arrays for Multi-dimensional Matrices.
  3. Simple and Flexible Detection of Contiguous Repeats Using a Suffix Tree (Preliminary Version).
  4. Efficient Parallel Algorithm for the Editing Distance between Ordered Trees.
  5. Aligning Alignments.
  6. A Very Fast String Matching Algorithm for Small Alphabeths and Long Patterns (Extended Abstract).
  7. Approximate Word Sequence Matching over Sparse Suffix Trees.
  8. Genome Halving.
  9. A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming.
  10. Fixed Topology Alignment with Recombination.
  11. Comparison of Coding DNA.
  12. Reporting Exact and Approximate Regular Expression Matches.
  13. A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching.
  14. A Dictionary Matching Algorithm Fast on the Average for Terms of Varying Length.
  15. A Rotation Invariant Filter for Two-Dimensional String Matching.
  16. An Approximate Oracle for Distance in Metric Spaces.
  17. Aligning DNA Sequences to Minimize the Change in Protein (Extended Abstract).

CPM 1997

  1. Aligning Coding DNA in the Presence of Frame-Shift Errors.
  2. Estimating the Probability of Approximate Matches.
  3. Trie-Based Data Structures for Sequence Assembly.
  4. External Inverse Pattern Matching.
  5. On Weak Circular Squares in Binary Words.
  6. On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts.
  7. Banishing Bias from Consensus Sequences.
  8. Space- and Time-Efficient Decoding with Canonical Huffman Trees.
  9. Iterative versus simultaneous Multiple Sequence Alignment (Abstract).
  10. An Improved Pattern Matching Algorithm for Strings in Terms of Straight-Line Programs.
  11. A New Algorithm for the Ordered Tree Inclusion Problem.
  12. Direct Construction of Compact Directed Acyclic Word Graphs.
  13. On Incremental Computation of Transitive Closure and Greedy Alignment.
  14. Flexible Identification of Structural Objects in Nucleic Acid Sequences: Palindromes, Mirror Repeats, Pseudoknots and Triple Helices.
  15. On the Nadeau-Taylor Theory of Conserved Chromosome Segments.
  16. Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem.
  17. Distributed Generation of Suffix Arrays.
  18. A Filter Method for the Weighted Local Similarity Search Problem.
  19. Efficient Algorithms for Approximate String Matching with Swaps (Extended Abstract).
  20. An Easy Case of Sorting by Reversals.
  21. Modern Comparative Lexicostatistics.
  22. Episode Matching.

CPM 1996

  1. Analysis of Two-Dimensional Approximate Pattern Matching Algorithms.
  2. Finite-State Computability of Annotations of Strings and Trees.
  3. Approximate Dictionary Queries.
  4. Graph Traversals, Genes, and Matroids: An Efficient Case of the Travelling Salesman Problem.
  5. Invariant Patterns in Crystal Lattices: Implications for Protein Folding Algorithms (Extended Abstract).
  6. A Faster Algorithm for Approximate String Matching.
  7. A 2 2/3-Approximation Algorithm for the Shortest Superstring Problem.
  8. Original Synteny.
  9. Improved Approximation Algorithms for Tree Alignment.
  10. The suffix Tree of a Tree and Minimizing Sequential Transducers.
  11. Alphabet Independent and Dictionary Scaled Matching.
  12. Spliced Alignment: A New Approach to Gene Recognition.
  13. Computing Discoveries in Molecular Biology (Abstract).
  14. Approximation Algorithms for Maximum Two-Dimensional Pattern Matching.
  15. Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract).
  16. Poisson Process Approximation for Repeats in One Sequence and Its Application to Sequencing by Hybridization.
  17. Approximate Multiple Strings Search.
  18. Efficient Parallel Algorithms for Tree Editing Problems.
  19. The Asymmetric Median Tree - A New model for Building Consensus Trees.
  20. Boyer-Moore Strategy to Efficient Approximate String Matching.
  21. Docking of Conformationally Flexible Proteins.
  22. Perfect Hashing for Strings: Formalization and Algorithms.
  23. Constructing Computer Virus Phylogenies.
  24. Approximate Pattern Matching in Directed Graphs.
  25. Fast Sorting by Reversal.
  26. A Double Combinatorial Approach to Discovering Patterns in Biological Sequences.
  27. Filtration with q-Samples in Approximate String Matching.
  28. Suffix Trees on Words.

CPM 1995

  1. Matching a Set of Strings with Variable Length Don’t Cares.
  2. Suffix Cactus: A Cross between Suffix Tree and Suffix Array.
  3. Fast Approximate Matching using Suffix Trees.
  4. Computing Similarity between RNA Strings.
  5. String Matching in Hypertext.
  6. Multiple Sequence Comparison: A Peptide Matching Approach.
  7. Common Subsequences and Supersequences and Their expected Length.
  8. On the Editing Distance between Undirected Acyclic Graphs and Related Problems.
  9. Polynomial-time Algorithm for Computing Translocation Distance between Genomes.
  10. Multi-Dimensional Pattern Matching with Dimensional Wildcards.
  11. A New Flexible Algorithm for the Longest Common Subsequence Problem.
  12. Pairwise Alignment with Scoring on Tuples.
  13. Three-Dimensional Pattern Matching in Protein Structure Analysis.
  14. Pattern Matching in Directed Graphs.
  15. Minimizing Phylogenetic Number to find Good Evolutionary Trees.
  16. On a Technique for Parsing a String (Abstract).
  17. An Efficient Algorithm for Developing Topological Valid Matchings.
  18. Matching Patterns of An Automaton.
  19. Approximation Algorithms for Multiple Sequence Alignment Under a Fixed Evolutionary Tree.
  20. New Results and Open Problems Related to Non-Standard Stringology.
  21. Of Chicken Teeth and Mouse Eyes, or Generalized Character Compatibility.
  22. Genome Analysis: Pattern Search in Biological Macromolecules.
  23. Making the Shortest-Paths Approach to Sum-of-Pairs Multiple Sequence Alignment More Space Efficient in Practice (Extended Abstract).
  24. Constant-Space String Matching with Smaller Number of Comparisons: Sequential Sampling.
  25. Pattern-Matching for Strings with Short Descriptions.
  26. On the Complexity of Comparing Evolutionary Trees (Extended Abstract).
  27. Efficient String Matching on Coded Texts.
  28. Smaller Representations for Finite-State Transducers and Finite-State Automata.
  29. Dictionary Loop-Up with Small Errors.

CPM 1994

  1. A Space Efficient Algorithm for Finding the Best Non-Overlapping Alignment Score.
  2. Query Primitives for Tree-Structured Data.
  3. Approximate String Matching and Local Similarity.
  4. Approximate String Matching with Don’t Care Characters.
  5. Recent Methods for RNA Modeling Using Stochastic Context-Free Grammars.
  6. Proximity Matching Using Fixed-Queries Trees.
  7. Approximation Algorithms for Multiple Sequence Alignment.
  8. Multiple Matching of Parameterized Patterns.
  9. A Context Dependent Method for Comparing Sequences.
  10. An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern.
  11. Dictionary-Matching on Unbounded Alphabets: Uniform Length Dictionaries.
  12. A Text Compression Scheme That Allows Fast Searching Directly in the Compressed File.
  13. A Lossy Data Compression Based on String Matching: Preliminary Analysis and Suboptimal Algorithms.
  14. Shortest Common Superstrings for Strings of Random Letters.
  15. Fast Identification of Approximately Matching Substrings.
  16. Efficient Bounds for Oriented Chromosome Inversion Distance.
  17. Maximal Common Subsequences and Minimal Common Supersequences.
  18. Computation of Squares in a String (Preliminary Version).
  19. Unit Route Upper Bound for String-Matching on Hypercube.
  20. Minimization of Sequential Transducers.
  21. Computing all Suboptimal Alignments in Linear Space.
  22. Matching with Matrix Norm Minimization.
  23. Polynomial-Time Algorithms for Computing Characteristic Strings.
  24. Parametric Recomuting in Alignment Graphs.
  25. The Parameterized Complexity of Sequence Alignment and Consensus.
  26. Alignment of Trees - An Alternative to Tree Edit.

CPM 1993

  1. A Fast Filtration Algorithm for the Substring Matching Problem.
  2. An Algorithm for Locating Non-Overlapping Regions of Maximum Alignment Score.
  3. A New Editing based Distance between Unordered Labeled Trees.
  4. The Maximum Weight Trace Problem in Multiple Sequence Alignment.
  5. Covering a String.
  6. 3-D Docking of Protein Molecules.
  7. A Linear Time Pattern Matching Algorithm Between a String and a Tree.
  8. Approximate String-Matching over Suffix Trees.
  9. A Unifying Look at d-Dimensional Periodicities and Space Coverings.
  10. Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes.
  11. An Algorithm for Approximate Tandem Repeats.
  12. Analysis of a String Edit Problem in a Probabilistic Framework (Extended Abstract).
  13. Multiple Sequence Comparison and n-Dimensional Image Reconstruction.
  14. Tight Comparison Bounds for the String Prefix-Matching Problem.
  15. Detecting False Matches in String Matching Algorithms.
  16. On the Worst-Case Behaviour of Some Approximation Algorithms for the Shortest Common Supersequence of k Strings.
  17. Minimal Separators of Two Words.
  18. On Suboptimal Alignments of Biological Sequences.
  19. Two Dimensional Pattern Matching in a Digitized Image.

CPM 1992

  1. Heaviest Increasing/Common Subsequence Problems.
  2. Fast Serial and Parallel Algorithms for Approximate Tree Matching with VLDC’s.
  3. Approximate Regular Expression Pattern Matching with Concave Gap Penalties.
  4. A Language Approach to String Searching Evaluation.
  5. Theoretical and Empirical Comparisons of Approximate String Matching Algorithms.
  6. Edit Distances for Genome Comparisons Based on Non-Local Operations.
  7. Computing Display Conflicts in String and Circular String Visualization.
  8. Fast and Practical Approximate String Matching.
  9. Pattern Matching With Mismatches: A Probabilistic Analysis and a Randomized Algorithm (Extended Abstract).
  10. Fast Multiple Keyword Searching.
  11. Color Set Size Problem with Application to String Matching.
  12. Matrix Longest Common Subsequence Problem, Duality and Hibert Bases.
  13. 3-D Substructure Matching in Protein Molecules.
  14. Multiple Alignment with Guaranteed Error Bounds and Communication Cost.
  15. Efficient Randomized Dictionary Matching Algorithms (Extended Abstract).
  16. Identifying Periodic Occurrences of a Template with Applications to Protein Structures.
  17. Grammatical Tree Matching.
  18. Dynamic Dictionary Matching with Failure Functions (Extended Abstract).
  19. Probabilistic Analysis of Generalized Suffix Trees (Extended Abstract).
  20. DZ: A Text Compression Algorithm For Natural Languages.
  21. From Regular Expressions to DFA’s Using Compressed NFA’s.
  22. Two Algorithms for the Longest Common Subsequence of Three (or More) Strings.
This site is open source. Improve this page.