StringologyTimes

Papers for stringologist (2020)

Contents

ALENEX 2020

  1. Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory.
  2. Engineering Top-Down Weight-Balanced Trees.
  3. RecSplit: Minimal Perfect Hashing via Recursive Splitting.
  4. Reverse-Safe Data Structures for Text Indexing.

APPROX-RANDOM 2020

  1. Improved Circular k-Mismatch Sketches.
  2. Lp Pattern Matching in a Stream.

BCB 2020

  1. SMART: SuperMaximal approximate repeats tool.

CPM 2020

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

CSR 2020

  1. Optimal Skeleton Huffman Trees Revisited.

CiE 2020

  1. Faster Online Computation of the Succinct Longest Previous Factor Array.

DCC 2020

  1. Approximating Optimal Bidirectional Macro Schemes.
  2. Bitvectors with Runs and the Successor/Predecessor Problem.
  3. Compact Representation of Graphs with Small Bandwidth and Treedepth.
  4. Compressing and Randomly Accessing Sequences (note).
  5. Decompressing Lempel-Ziv Compressed Text.
  6. Edge Minimization in de Bruijn Graphs.
  7. Grammar Compression with Probabilistic Context-Free Grammar.
  8. On Dynamic Succinct Graph Representations.
  9. Pattern Search in Grammar-Compressed Graphs.
  10. Practical Repetition-Aware Grammar Compression.
  11. Re-Pair in Small Space.
  12. Revisiting Compact RDF Stores Based on k2-Trees.
  13. Semantrix: A Compressed Semantic Matrix.
  14. Towards Better Compressed Representations.
  15. c-Trie++: A Dynamic Trie Tailored for Fast Prefix Searches.

DLT 2020

  1. Scattered Factor-Universality of Words.

ESA 2020

  1. Efficient Computation of 2-Covers of a String.
  2. Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing.
  3. New Binary Search Tree Bounds via Geometric Inversions.
  4. On the Complexity of BWT-Runs Minimization via Alphabet Reordering.
  5. Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
  6. The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance.
  7. The Number of Repetitions in 2D-Strings.

Euro-Par 2020

  1. LCP-Aware Parallel String Sorting.

FOCS 2020

  1. Edit Distance in Near-Linear Time: it’s a Constant Factor.
  2. Faster Approximate Pattern Matching: A Unified Approach.
  3. Lazy Search Trees.
  4. On One-way Functions and Kolmogorov Complexity.
  5. Resolution of the Burrows-Wheeler Transform Conjecture.
  6. Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.

FSTTCS 2020

  1. String Indexing for Top-k Close Consecutive Occurrences.

ICALP 2020

  1. Dynamic Longest Common Substring in Polylogarithmic Time.
  2. Space Efficient Construction of Lyndon Arrays in Linear Time.

ICDT 2020

  1. Optimal Joins Using Compact Data Structures.

ISAAC 2020

  1. A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem.
  2. A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length.
  3. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs.
  4. Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees.
  5. Efficient Labeling for Reachability in Directed Acyclic Graphs.
  6. Enumerating Range Modes.
  7. Random Access in Persistent Strings.
  8. Update Query Time Trade-Off for Dynamic Suffix Arrays.

ITCS 2020

  1. Unexpected Power of Random Strings.

IWOCA 2020

  1. Optimal In-place Algorithms for Basic Graph Problems.

LATA 2020

  1. Lyndon Words versus Inverse Lyndon Words: Queries on Suffixes and Bordered Words.
  2. On Collapsing Prefix Normal Words.

LATIN 2020

  1. Batched Predecessor and Sorting with Size-Priced Information in External Memory.
  2. On the Collection of Fringe Subtrees in Random Binary Trees.
  3. Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries.
  4. Towards a Definitive Measure of Repetitiveness.

SEA 2020

  1. Fast and Linear-Time String Matching Algorithms Based on the Distances of q-Gram Occurrences.
  2. Fast and Simple Compact Hashing via Bucketing.
  3. Indexing Compressed Text: A Tale of Time and Space (Invited Talk).
  4. Pattern Discovery in Colored Strings.
  5. Zipping Segment Trees.

SODA 2020

  1. A Lower Bound for Jumbled Indexing.
  2. Better Data Structures for Colored Orthogonal Range Reporting.
  3. Combinatorial generation via permutation languages.
  4. Competitive Online Search Trees on Trees.
  5. Improved Algorithms for Edit Distance and LCS: Beyond Worst Case.
  6. Locally Consistent Parsing for Text Indexing in Small Space.
  7. Reducing approximate Longest Common Subsequence to approximate Edit Distance.
  8. Regular Languages meet Prefix Sorting.

SOFSEM 2020

  1. Fast Indexes for Gapped Pattern Matching.
  2. Faster STR-EC-LCS Computation.
  3. Minimal Unique Substrings and Minimal Absent Words in a Sliding Window.
  4. Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching.

SOSA 2020

  1. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort.

SPIRE 2020

  1. A Comparison of Empirical Tree Entropies.
  2. Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction.
  3. An Efficient Elastic-Degenerate Text Index? Not Likely.
  4. Approximating the Anticover of a String.
  5. Computing Covers Under Substring Consistent Equivalence Relations.
  6. Contextual Pattern Matching.
  7. Efficient Construction of Hierarchical Overlap Graphs.
  8. Efficient Enumeration of Distinct Factors Using Package Representations.
  9. Internal Quasiperiod Queries.
  10. Longest Square Subsequence Problem Revisited.
  11. Lyndon Words, the Three Squares Lemma, and Primitive Squares.
  12. Measuring Controversy in Social Networks Through NLP.
  13. Multidimensional Period Recovery.
  14. Navigating Forest Straight-Line Programs in Constant Time.
  15. On Repetitiveness Measures of Thue-Morse Words.
  16. Practical Random Access to SLP-Compressed Texts.
  17. Pre-indexing Pruning Strategies.
  18. Relative Lempel-Ziv Compression of Suffix Arrays.
  19. Smaller Fully-Functional Bidirectional BWT Indexes.
  20. Tailoring r-index for Document Listing Towards Metagenomics Applications.
  21. Towards Efficient Interactive Computation of Dynamic Time Warping Distance.

STACS 2020

  1. A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem.
  2. Generalised Pattern Matching Revisited.
  3. Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements.
  4. String Indexing with Compressed Patterns.
  5. Using Statistical Encoding to Achieve Tree Succinctness Never Seen Before.

STOC 2020

  1. Approximating text-to-pattern Hamming distances.
  2. Constant factor approximations to edit distance on far input pairs in nearly linear time.
  3. Constant-factor approximation of near-linear edit distance in near-linear time.
  4. Lower bound for succinct range minimum query.
  5. Nearly optimal static Las Vegas succinct dictionary.

SWAT 2020

  1. Space-Efficient Data Structures for Lattices.

SoCG 2020

  1. Four-Dimensional Dominance Range Reporting in Linear Space.
  2. Further Results on Colored Range Searching.

Stringology 2020

  1. Conversion of Finite Tree Automata to Regular Tree Expressions By State Elimination.
  2. Enumerative Data Compression with Non-Uniquely Decodable Codes.
  3. Fast Exact Pattern Matching in a Bitstream and 256-ary Strings.
  4. Fast Practical Computation of the Longest Common Cartesian Substrings of Two Strings.
  5. Forward Linearised Tree Pattern Matching Using Tree Pattern Border Array.
  6. Greedy versus Optimal Analysis of Bounded Size Dictionary Compression and On-the-Fly Distributed Computing.
  7. Left Lyndon Tree Construction.
  8. New Compression Schemes for Natural Number Sequences.
  9. On Arithmetically Progressed Suffix Arrays.
  10. Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings.
  11. Re-Pair in Small Space.
  12. Reducing Time and Space in Indexed String Matching by Characters Distance Text Sampling.
  13. Simple KMP Pattern-Matching on Indeterminate Strings.
  14. Tune-up for the Dead-Zone Algorithm.

TAMC 2020

  1. Partial Sums on the Ultra-Wide Word RAM.

WABI 2020

  1. Linear Time Construction of Indexable Founder Block Graphs.

WALCOM 2020

  1. Fast Multiple Pattern Cartesian Tree Matching.
  2. Faster Privacy-Preserving Computation of Edit Distance with Moves.
  3. Generalized Dictionary Matching Under Substring Consistent Equivalence Relations.
  4. Shortest Covers of All Cyclic Shifts of a String.

ACM J. Exp. Algorithmics 2020

  1. Dynamic Path-decomposed Tries.
  2. Property Suffix Array with Applications in Indexing Weighted Sequences.

ACM Trans. Algorithms 2020

  1. A Linear-Time Algorithm for Seeds Computation.
  2. Deterministic Sparse Suffix Sorting in the Restore Model.
  3. Linear-time String Indexing and Analysis in Small Space.
  4. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can).

Algorithmica 2020

  1. Compressed Dynamic Range Majority and Minority Data Structures.
  2. Computational Aspects of Ordered Integer Partitions with Bounds.
  3. Dynamic and Internal Longest Common Substring.
  4. Fast Compressed Self-indexes with Deterministic Linear-Time Construction.
  5. Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts.
  6. Lempel-Ziv-Like Parsing in Small Space.

Algorithms 2020

  1. A New Lossless DNA Compression Algorithm Based on A Single-Block Encoding Scheme.
  2. Editorial: Special Issue on Data Compression Algorithms and Their Applications.
  3. Efficient Data Structures for Range Shortest Unique Substring Queries.
  4. More Time-Space Tradeoffs for Finding a Shortest Unique Substring.
  5. Practical Grammar Compression Based on Maximal Repeats.

Algorithms Mol. Biol. 2020

  1. Finding all maximal perfect haplotype blocks in linear time.
  2. gsufsort: constructing suffix arrays, LCP arrays and BWTs for string collections.

BMC Bioinform. 2020

  1. Variable-order reference-free variant discovery with the Burrows-Wheeler Transform.

Bioinform. 2020

  1. SMART: SuperMaximal approximate repeats tool.

CoRR 2020

  1. $O(\log \log n)$ Worst-Case Local Decoding and Update Efficiency for Data Compression.
  2. 2-Dimensional Palindromes with k Mismatches.
  3. A Big Data Approach for Sequences Indexing on the Cloud via Burrows Wheeler Transform.
  4. A Case for Partitioned Bloom Filters.
  5. A Data-Structure for Approximate Longest Common Subsequence of A Set of Strings.
  6. A Dynamic Space-Efficient Filter with Constant Time Operations.
  7. A Fast Algorithm for Online k-servers Problem on Trees.
  8. A Fast Randomized Algorithm for Finding the Maximal Common Subsequences.
  9. A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem.
  10. A Hybrid Approach to Temporal Pattern Matching.
  11. A New Approach to Regular & Indeterminate Strings.
  12. A New Upper Bound for Separating Words.
  13. A Normal Sequence Compressed by PPM* but not by Lempel-Ziv 78.
  14. A Pedagogically Sound yet Efficient Deletion algorithm for Red-Black Trees: The Parity-Seeking Delete Algorithm.
  15. A Simple Sublinear Algorithm for Gap Edit Distance.
  16. A Tale of Two Trees: New Analysis for AVL Tree and Binary Heap.
  17. A grammar compressor for collections of reads with applications to the construction of the BWT.
  18. A reduction of the dynamic time warping distance to the longest increasing subsequence length.
  19. Access-Adaptive Priority Search Tree.
  20. Adaptive Fibonacci and Pairing Heaps.
  21. Age-Partitioned Bloom Filters.
  22. An Efficient Implementation of Manacher’s Algorithm.
  23. An Improved Algorithm for Dynamic Set Cover.
  24. An Improved Sketching Bound for Edit Distance.
  25. An inequality for the number of periods in a word.
  26. Analysis and Evaluation of Non-Blocking Interpolation Search Trees.
  27. Approximating LCS in Linear Time: Beating the √n Barrier.
  28. Approximating Optimal Bidirectional Macro Schemes.
  29. Approximating Text-to-Pattern Distance via Dimensionality Reduction.
  30. Approximating Text-to-Pattern Hamming Distances.
  31. Approximating longest common substring with $k$ mismatches: Theory and practice.
  32. Arithmetic Binary Search Trees: Static Optimality in the Matching Model.
  33. Beyond the Worst-Case Analysis of Algorithms (Introduction).
  34. Bitvectors with runs and the successor/predecessor problem.
  35. Black-White Array: A New Data Structure for Dynamic Data Sets.
  36. Blocksequences of k-local Words.
  37. Breadth-First Rank/Select in Succinct Trees and Distance Oracles for Interval Graphs.
  38. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort.
  39. Cadences in Grammar-Compressed Strings.
  40. Chaining with overlaps revisited.
  41. Chronofold: a data structure for versioned text.
  42. Classical and Quantum Algorithms for Constructing Text from Dictionary Problem.
  43. Communication-Efficient String Sorting.
  44. Competitive Data-Structure Dynamization.
  45. Compressed Data Structures for Binary Relations in Practice.
  46. Compression with wildcards: All spanning trees.
  47. Computing Covers under Substring Consistent Equivalence Relations.
  48. Computing Palindromic Trees for a Sliding Window and Its Applications.
  49. Computing the rearrangement distance of natural genomes.
  50. Concurrent Disjoint Set Union.
  51. Contextual Pattern Matching.
  52. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs.
  53. Counting Distinct Patterns in Internal Dictionary Matching.
  54. Counting ternary square-free words quickly.
  55. DAWGs for parameterized matching: online construction and related indexing structures.
  56. Data Structure Primitives on Persistent Memory: An Evaluation.
  57. Decode efficient prefix codes.
  58. Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences.
  59. Dynamic Boundary Time Warping for Sub-sequence Matching with Few Examples.
  60. Dynamic Longest Common Substring in Polylogarithmic Time.
  61. Dynamic Similarity Search on Integer Sketches.
  62. Edit Distance in Near-Linear Time: it’s a Constant Factor.
  63. Efficient Constrained Pattern Mining Using Dynamic Item Ordering for Explainable Classification.
  64. Efficient Semi-External Depth-First Search.
  65. Efficient and Effective Query Auto-Completion.
  66. Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences.
  67. Efficient tree-structured categorical retrieval.
  68. Efficiently Testing Simon’s Congruence.
  69. Engineering Faster Sorters for Small Sets of Items.
  70. Enumeration of LCP values, LCP intervals and Maximal repeats in BWT-runs Bounded Space.
  71. Erdös-Szekeres Partitioning Problem.
  72. Extremal overlap-free and extremal β-free binary words.
  73. Fast Generation of Big Random Binary Trees.
  74. Fast Indexes for Gapped Pattern Matching.
  75. Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing.
  76. Fast and Simple Modular Subset Sum.
  77. Fast and linear-time string matching algorithms based on the distances of q-gram occurrences.
  78. Faster Approximate Pattern Matching: A Unified Approach.
  79. Faster Binary Mean Computation Under Dynamic Time Warping.
  80. Faster Queries on BWT-runs Compressed Indexes.
  81. Faster STR-EC-LCS Computation.
  82. Fine-Grained Complexity of Regular Expression Pattern Matching and Membership.
  83. Four-Dimensional Dominance Range Reporting in Linear Space.
  84. Fully Dynamic Approximation of LIS in Polylogarithmic Time.
  85. Further Results on Colored Range Searching.
  86. Galloping in natural merge sorts.
  87. Generalised Pattern Matching Revisited.
  88. Generalized Sorting with Predictions.
  89. Generating a Gray code for prefix normal words in amortized polylogarithmic time per word.
  90. Grammar Compression By Induced Suffix Sorting.
  91. Grammar compression with probabilistic context-free grammar.
  92. Grammar-Compressed Indexes with Logarithmic Search Time.
  93. Grammar-compressed Self-index with Lyndon Words.
  94. Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring.
  95. Hidden Words Statistics for Large Patterns.
  96. Huskysort.
  97. Impossibility Results for Grammar-Compressed Linear Algebra.
  98. Improved Circular k-Mismatch Sketches.
  99. Improved Dynamic Algorithms for Longest Increasing Subsequence.
  100. In-Place Bijective Burrows-Wheeler Transforms.
  101. Incremental Multiple Longest Common Sub-Sequences.
  102. Indexing Highly Repetitive String Collections.
  103. Integer Division by Constants: Optimal Bounds.
  104. Internal Quasiperiod Queries.
  105. LCP-Aware Parallel String Sorting.
  106. Lazy Search Trees.
  107. Learning Directly from Grammar Compressed Text.
  108. Learning Halfspaces With Membership Queries.
  109. Left Lyndon tree construction.
  110. Lengths of extremal square-free ternary words.
  111. Linear Time Construction of Indexable Founder Block Graphs.
  112. Local Editing in LZ-End Compressed Data.
  113. Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring.
  114. Longest Common Subsequence in Sublinear Space.
  115. Longest Square Subsequence Problem Revisited.
  116. Lossless Compression of Deep Neural Networks.
  117. Lower Bound for Succinct Range Minimum Query.
  118. Lyndon Words, the Three Squares Lemma, and Primitive Squares.
  119. Multiset Synchronization with Counting Cuckoo Filters.
  120. Near-Linear Time Edit Distance for Indel Channels.
  121. New Algorithms and Lower Bounds for LIS Estimation.
  122. New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring.
  123. New Data Structures for Orthogonal Range Reporting and Range Minima Queries.
  124. No Repetition: Fast Streaming with Highly Concentrated Hashing.
  125. Notes on Randomized Algorithms.
  126. Novel Results on the Number of Runs of the Burrows-Wheeler-Transform.
  127. On Extensions of Maximal Repeats in Compressed Strings.
  128. On Indexing and Compressing Finite Automata.
  129. On Locating Paths in Compressed Cardinal Trees.
  130. On One-way Functions and Kolmogorov Complexity.
  131. On Rearrangement of Items Stored in Stacks.
  132. On Two Measures of Distance between Fully-Labelled Trees.
  133. On Weighted Prefix Normal Words.
  134. On prefix palindromic length of automatic words.
  135. On repetitiveness measures of Thue-Morse words.
  136. On the binomial equivalence classes of finite words.
  137. On the improvement of the in-place merge algorithm parallelization.
  138. On the parameterized complexity of the Minimum Path Cover problem in DAGs.
  139. Optimal Entropy Compression and Purification in Quantum Bits.
  140. Optimal Skeleton Huffman Trees Revisited.
  141. Optimal construction of a layer-ordered heap.
  142. Optimal selection on X+Y simplified with layer-ordered heaps.
  143. PFP Data Structures.
  144. PHONI: Streamed Matching Statistics with Multi-Genome References.
  145. Palindromic Length of Words with Many Periodic Palindromes.
  146. Palindromic k-Factorization in Pure Linear Time.
  147. Pattern Discovery in Colored Strings.
  148. Pattern Masking for Dictionary Matching.
  149. Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings.
  150. Primitive Sets of Words.
  151. Pushdown and Lempel-Ziv Depth.
  152. Quantum Algorithm for Lexicographically Minimal String Rotation.
  153. Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems.
  154. Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language.
  155. Quantum string comparison method.
  156. Random Access in Persistent Strings.
  157. Reconstructing Words from Right-Bounded-Block Words.
  158. Revisiting compact RDF stores based on k2-trees.
  159. SARS-CoV-2 Coronavirus Data Compression Benchmark.
  160. SOPanG 2: online searching over a pan-genome without false positives.
  161. Scattered Factor-Universality of Words.
  162. Scout Algorithm For Fast Substring Matching.
  163. Searching and Sorting with O(n2) processors in O(1) time.
  164. Selectable Heaps and Optimal Lazy Search Trees.
  165. Semantrix: A Compressed Semantic Matrix.
  166. Shorter Labels for Routing in Trees.
  167. Simulation computation in grammar-compressed graphs.
  168. Small Longest Tandem Scattered Subsequences.
  169. Soft Sequence Heaps.
  170. Solving Shisen-Sho boards.
  171. Sorting Lists with Equal Keys Using Mergesort in Linear Time.
  172. Sorting Short Keys in Circuits of Size o(n log n).
  173. Space Efficient Deterministic Approximation of String Measures.
  174. Space efficient merging of de Bruijn graphs and Wheeler graphs.
  175. Space/time-efficient RDF stores based on circular suffix sorting.
  176. Splay trees on trees.
  177. Still Simpler Static Level Ancestors.
  178. Storing Set Families More Compactly with Top ZDDs.
  179. Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS.
  180. String Attractors for Automatic Sequences.
  181. String Indexing for Top-k Close Consecutive Occurrences.
  182. String Sanitization Under Edit Distance: Improved and Generalized.
  183. Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs.
  184. Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.
  185. Subpath Queries on Compressed Graphs: a Survey.
  186. Substring Complexity in Sublinear Space.
  187. Substring Query Complexity of String Reconstruction.
  188. Succinct Dynamic Ordered Sets with Random Access.
  189. Succinct Trit-array Trie for Scalable Trajectory Similarity Search.
  190. Sumsets of Wythoff Sequences, Fibonacci Representation, and Beyond.
  191. TADOC: Text Analytics Directly on Compression.
  192. Tailoring r-index for metagenomics.
  193. The Bloom Tree.
  194. The Edit Distance to k-Subsequence Universality.
  195. The K-Centre Problem for Necklaces.
  196. The Longest Run Subsequence Problem: Further Complexity Results.
  197. The Number of Repetitions in 2D-Strings.
  198. The Parameterized Suffix Tray.
  199. The Simplest Binary Word with Only Three Squares.
  200. The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time.
  201. The n-dimensional k-vector and its application to orthogonal range searching.
  202. Tight Bound for the Number of Distinct Palindromes in a Tree.
  203. Time-Space Tradeoffs for Finding a Long Common Substring.
  204. Towards Efficient Interactive Computation of Dynamic Time Warping Distance.
  205. Translating Between Wavelet Tree and Wavelet Matrix Construction.
  206. Two halves of a meaningful text are statistically different.
  207. Uniform Linked Lists Contraction.
  208. Update Query Time Trade-off for dynamic Suffix Arrays.
  209. Wheeler Languages.
  210. Zipping Segment Trees.
  211. Zuckerli: A New Compressed Representation for Graphs.
  212. k-Approximate Quasiperiodicity under Hamming and Edit Distance.

Discret. Appl. Math. 2020

  1. A brief history of parameterized matching problems.
  2. A formal framework for Stringology.
  3. A resource-frugal probabilistic dictionary and applications in bioinformatics.
  4. Accelerated partial decoding in wavelet trees.
  5. Direct merging of delta encoded files.
  6. Dynamic determination of variable sizes of chunks in a deduplication system.
  7. Dynamic index and LZ factorization in compressed space.
  8. Generating all minimal petri net unsolvable binary words.
  9. Improved online algorithms for jumbled matching.
  10. On approximate enhanced covers under Hamming distance.
  11. On the computational complexity of closest genome problems.
  12. Preface: Stringology Algorithms.
  13. The order-preserving pattern matching problem in practice.

Fundam. Informaticae 2020

  1. Comparing Degenerate Strings.

Inf. 2020

  1. On the Randomness of Compressed Data.

Inf. Comput. 2020

  1. A compressed dynamic self-index for highly repetitive text collections.
  2. Absent words in a sliding window with applications.
  3. Compact and succinct data structures for multidimensional orthogonal range searching.
  4. Computation over compressed data.
  5. Indexing weighted sequences: Neat and efficient.
  6. Online recognition of dictionary with one gap.
  7. Streaming k-mismatch with error correcting and applications.
  8. String periods in the order-preserving model.

Int. J. Found. Comput. Sci. 2020

  1. Efficient Identification of k-Closed Strings.

J. ACM 2020

  1. Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space.

J. Comput. Biol. 2020

  1. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment.
  2. Matching Reads to Many Genomes with the r-Index.

J. Signal Process. Syst. 2020

  1. An Efficient High-Throughput LZ77-Based Decompressor in Reconfigurable Logic.

Proc. VLDB Endow. 2020

  1. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds.

Theor. Comput. Sci. 2020

  1. A linear-space data structure for range-LCP queries in poly-logarithmic time.
  2. Approximate pattern matching on elastic-degenerate text.
  3. Compressed range minimum queries.
  4. Efficient computation of longest single-arm-gapped palindromes in a string.
  5. Faster algorithms for 1-mappability of a sequence.
  6. Finding patterns and periods in Cartesian tree matching.
  7. Generating a Gray code for prefix normal words in amortized polylogarithmic time per word.
  8. Lightweight merging of compressed indices based on BWT variants.
  9. Longest property-preserved common factor: A new string-processing framework.
  10. Parallel computation of the Burrows Wheeler Transform in compact space.
  11. Refining the r-index.
  12. Space-efficient algorithms for computing minimal/shortest unique substrings.
  13. The Alternating BWT: An algorithmic perspective.
  14. Tree path majority data structures.
  15. Two-dimensional maximal repetitions.
  16. Universal reconstruction of a string.

Theory Comput. Syst. 2020

  1. Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings.
This site is open source. Improve this page.