StringologyTimes

CPM for Stringologist

CPM 2024

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

CPM 2023

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

CPM 2022

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

CPM 2021

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

CPM 2020

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

CPM 2019

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

CPM 2018

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

CPM 2017

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

CPM 2016

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

CPM 2015

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

CPM 2014

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

CPM 2013

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

CPM 2012

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

CPM 2011

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

CPM 2010

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

CPM 2009

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

CPM 2008

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

CPM 2007

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

CPM 2006

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

CPM 2005

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

CPM 2004

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

CPM 2003

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

CPM 2002

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

CPM 2001

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

CPM 2000

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

CPM 1999

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

CPM 1998

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

CPM 1997

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

CPM 1996

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

CPM 1995

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

CPM 1994

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

CPM 1993

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

CPM 1992

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