StringologyTimes

Papers for stringologist (2022)

Contents

CPM 2022

  1. Bi-Directional r-Indexes.
  2. Longest Palindromic Substring in Sublinear Time.
  3. The Dynamic k-Mismatch Problem.

DCC 2022

  1. A Benchmark of Entropy Coders for the Compression of Genome Sequencing Data.
  2. Burrows-Wheeler Transform on Purely Morphic Words.
  3. CSTs for Terabyte-Sized Data.
  4. Compressing the Tree of Canonical Huffman Coding.
  5. Computing Lexicographic Parsings.
  6. Computing Matching Statistics on Repetitive Texts.
  7. Converting RLBWT to LZ77 in smaller space.
  8. FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns.
  9. Fast Coding of Haar Wavelet Trees.
  10. Graphs can be succinctly indexed for pattern matching in $O(\vert E\vert ^{2}+\vert V\vert ^{5/2})$ time.
  11. HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances.
  12. Linear-time Minimization of Wheeler DFAs.
  13. Lower Bounds for Lexicographical DFS Data Structures.
  14. On Dynamic Bitvector Implementations.
  15. On different variants of the Burrows-Wheeler-Transform of string collections.
  16. RLBWT Tricks.
  17. Selective Weighted Adaptive Coding.
  18. Simple Worst-Case Optimal Adaptive Prefix-Free Coding.
  19. Succinct Data Structure for Path Graphs.
  20. x3: Lossless Data Compressor.

DLT 2022

  1. Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words.
  2. Prefix Palindromic Length of the Sierpinski Word.

ESA 2022

  1. An Improved Algorithm for Finding the Shortest Synchronizing Words.
  2. Approximate Circular Pattern Matching.
  3. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.
  4. Computing NP-Hard Repetitiveness Measures via MAX-SAT.
  5. Distinct Elements in Streams: An Algorithm for the (Text) Book.
  6. Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold.
  7. Lyndon Arrays Simplified.
  8. Simple Worst-Case Optimal Adaptive Prefix-Free Coding.

FOCS 2022

  1. Estimating the Longest Increasing Subsequence in Nearly Optimal Time.
  2. Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices.
  3. Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.
  4. Online List Labeling: Breaking the log2n Barrier.
  5. Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract).
  6. Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.

HCVS/VPT@ETAPS 2022

  1. Reversible Programming: A Case Study of Two String-Matching Algorithms.

ICALP 2022

  1. An Optimal-Time RLBWT Construction in BWT-Runs Bounded Space.
  2. Fully Functional Parameterized Suffix Trees in Compact Space.
  3. Galloping in Fast-Growth Natural Merge Sorts.
  4. Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding.
  5. Improved Sublinear-Time Edit Distance for Preprocessed Strings.
  6. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds.

ISAAC 2022

  1. Computing Palindromes on a Trie in Linear Time.
  2. External-Memory Dictionaries with Worst-Case Update Cost.
  3. On the Complexity of Tree Edit Distance with Variables.
  4. Simple Order-Isomorphic Matching Index with Expected Compact Space.
  5. Succinct List Indexing in Optimal Time.

ISBRA 2022

  1. Optimal Sequence Alignment to ED-Strings.

IWCIA 2022

  1. Lyndon Partial Words and Arrays with Applications.

IWOCA 2022

  1. Computing Longest (Common) Lyndon Subsequences.
  2. Linear Time Construction of Indexable Elastic Founder Graphs.
  3. Practical Space-Efficient Index for Structural Pattern Matching.
  4. Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings.
  5. Space-Efficient B Trees via Load-Balancing.

LATIN 2022

  1. Elastic-Degenerate String Matching with 1 Error.
  2. Near-Optimal Search Time in δ-Optimal Space.
  3. Space-Efficient Data Structure for Next/Previous Larger/Smaller Value Queries.
  4. String Attractors and Infinite Words.

MFCS 2022

  1. On Uniformization in the Full Binary Tree.
  2. Streaming Word Problems.

NCMA 2022

  1. Combinatorial Algorithms for Subsequence Matching: A Survey.

SEA 2022

  1. Computing Maximal Unique Matches with the r-Index.
  2. RLBWT Tricks.

SODA 2022

  1. A Lower Bound for the n-queens Problem.
  2. An Improved Algorithm for The k-Dyck Edit Distance Problem.
  3. An Upper Bound and Linear-Space Queries on the LZ-End Parsing.
  4. Average Sensitivity of Dynamic Programming.
  5. Enumerating k-SAT functions.
  6. How Compression and Approximation Affect Efficiency in String Distance Measures.
  7. How many Clusters? - An algorithmic answer.
  8. Pattern Matching on Grammar-Compressed Strings in Linear Time.
  9. Selectable Heaps and Optimal Lazy Search Trees.
  10. Simulating a stack using queues.
  11. Splay trees on trees.
  12. Streaming Regular Expression Membership and Pattern Matching.

SOSA 2022

  1. Faster Exponential Algorithm for Permutation Pattern Matching.
  2. Simpler Adjacency Labeling for Planar Graphs with B-Trees.

SPIRE 2022

  1. KATKA: A KRAKEN-Like Tool with k Given at Query Time.
  2. Matching Patterns with Variables Under Edit Distance.
  3. Online Algorithms for Finding Distinct Substrings with Length and Multiple Prefix and Suffix Conditions.

STACS 2022

  1. Existential Definability over the Subword Ordering.
  2. Probabilistic vs Deterministic Gamblers.

STOC 2022

  1. Almost-optimal sublinear-time edit distance in the low distance regime.
  2. Dynamic suffix array with polylogarithmic queries and updates.
  3. Explicit binary tree codes with sub-logarithmic size alphabet.
  4. Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios.
  5. On the optimal time/space tradeoff for hash tables.

SWAT 2022

  1. Predecessor on the Ultra-Wide Word RAM.
  2. Unit-Disk Range Searching and Applications.

WABI 2022

  1. Eulertigs: Minimum Plain Text Representation of k-mer Sets Without Repetitions in Linear Time.
  2. Fast Gapped k-mer Counting with Subdivided Multi-Way Bucketed Cuckoo Hash Tables.
  3. Haplotype Threading Using the Positional Burrows-Wheeler Transform.
  4. Locality-Sensitive Bucketing Functions for the Edit Distance.
  5. On Weighted k-mer Dictionaries.
  6. Prefix-Free Parsing for Building Large Tunnelled Wheeler Graphs.
  7. Suffix Sorting via Matching Statistics.
  8. Toward Optimal Fingerprint Indexing for Large Scale Genomics.
  9. phyBWT: Alignment-Free Phylogeny via eBWT Positional Clustering.

ACM Comput. Surv. 2022

  1. Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures.
  2. Indexing Highly Repetitive String Collections, Part II: Compressed Indexes.

ACM J. Exp. Algorithmics 2022

  1. Grammar Compression by Induced Suffix Sorting.

ACM Trans. Algorithms 2022

  1. A Simple Algorithm for Optimal Search Trees with Two-way Comparisons.

Algorithmica 2022

  1. A Faster Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length.
  2. Adaptive Succinctness.
  3. Computing Minimal Unique Substrings for a Sliding Window.
  4. Efficient Computation of Sequence Mappability.
  5. Fast and Longest Rollercoasters.
  6. Space Efficient Merging of de Bruijn Graphs and Wheeler Graphs.
  7. Streaming Dictionary Matching with Mismatches.

Algorithms Mol. Biol. 2022

  1. Space-efficient representation of genomic k-mer count tables.

Appl. Soft Comput. 2022

  1. Graph search and variable neighborhood search for finding constrained longest common subsequences in artificial and real gene sequences.

Bioinform. 2022

  1. Fast and compact matching statistics analytics.

CoRR 2022

  1. 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time.
  2. A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits.
  3. A New Class of String Transformations for Compressed Text Indexing.
  4. A Simpler Proof that Pairing Heaps Take O(1) Amortized Time per Insertion.
  5. A Stack-Free Traversal Algorithm for Left-Balanced k-d Trees.
  6. A Work-Efficient Parallel Algorithm for Longest Increasing Subsequence.
  7. A fast and simple O(z log n)-space index for finding approximately longest common substrings.
  8. A nearly optimal randomized algorithm for explorable heap selection.
  9. Abelian Combinatorics on Words: a Survey.
  10. Algorithm to derive shortest edit script using Levenshtein distance algorithm.
  11. Almost optimal searching of maximal subrepetitions in a word.
  12. An Algorithmic Bridge Between Hamming and Levenshtein Distances.
  13. An Improved Algorithm for Finding the Shortest Synchronizing Words.
  14. An n Hk-compressed searchable partial-sums data structure for static sequences of sublogarithmic positive integers.
  15. Antisquares and Critical Exponents.
  16. Approximate Circular Pattern Matching.
  17. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.
  18. Approximating binary longest common subsequence in near-linear time.
  19. Asymptotic bounds for the number of closed and privileged words.
  20. Augmented Thresholds for MONI.
  21. Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev.
  22. Balancing Run-Length Straight-Line Programs.
  23. Binary codes that do not preserve primitivity.
  24. Bounds and Estimates on the Average Edit Distance.
  25. CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams.
  26. Cache-Oblivious Representation of B-Tree Structures.
  27. Co-lexicographically ordering automata and regular languages. Part I.
  28. Comparing Two Counting Methods for Estimating the Probabilities of Strings.
  29. Complement Avoidance in Binary Words.
  30. Computing MEMs on Repetitive Text Collections.
  31. Computing Maximal Unique Matches with the r-index.
  32. Computing NP-hard Repetitiveness Measures via MAX-SAT.
  33. Computing all-vs-all MEMs in run-length encoded collections of HiFi reads.
  34. Computing maximal generalized palindromes.
  35. Computing palindromes on a trie in linear time.
  36. Computing the Parameterized Burrows-Wheeler Transform Online.
  37. Computing the optimal BWT of very large string collections.
  38. Concurrent Size.
  39. Constant-delay enumeration for SLP-compressed documents.
  40. Convergence of the number of period sets in strings.
  41. Cut-Down de Bruijn Sequences.
  42. Designing a parallel suffix sort.
  43. Double-Ended Palindromic Trees: A Linear-Time Data Structure and Its Applications.
  44. Dynamic data structures for parameterized string problems.
  45. Efficient Algorithms for Sorting in Trees.
  46. Efficient Construction of the BWT for Repetitive Text Using String Compression.
  47. Elastic-Degenerate String Matching with 1 Error.
  48. Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors.
  49. Engineering faster double-array Aho-Corasick automata.
  50. External-memory dictionaries with worst-case update cost.
  51. Fast Circular Pattern Matching.
  52. Fast Exact String to D-Texts Alignments.
  53. Fast detection of specific fragments against a set of sequences.
  54. Faster Min-Plus Product for Monotone Instances.
  55. Faster Pattern Matching under Edit Distance.
  56. Gapped String Indexing in Subquadratic Space and Sublinear Query Time.
  57. Hierarchical Relative Lempel-Ziv Compression.
  58. High Performance Construction of RecSplit Based Minimal Perfect Hash Functions.
  59. Hinted Dictionaries: Efficient Functional Ordered Sets and Maps.
  60. Implementing the Comparison-Based External Sort.
  61. Improved Sublinear-Time Edit Distance for Preprocessed Strings.
  62. Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices.
  63. Inferring strings from position heaps in linear time.
  64. Internal Longest Palindrome Queries in Optimal Time.
  65. KATKA: A KRAKEN-like tool with k given at query time.
  66. L-systems for Measuring Repetitiveness.
  67. Learning Augmented Binary Search Trees.
  68. Lie Complexity of Sturmian Words.
  69. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds.
  70. Locality-Preserving Minimal Perfect Hashing of k-mers.
  71. Longest Common Subsequence: Tabular vs. Closed-Form Equation Computation of Subsequence Probability.
  72. Lower Bounds for Sorting 16, 17, and 18 Elements.
  73. MARIA: Multiple-alignment r-index with aggregation.
  74. Matching Patterns with Variables Under Edit Distance.
  75. Maximal Closed Substrings.
  76. Merging Sorted Lists of Similar Strings.
  77. Multiway Powersort.
  78. Near-Optimal Search Time in δ-Optimal Space.
  79. New Parallel Order Maintenance Data Structure.
  80. Note on a Fibonacci Parity Sequence.
  81. On extended boundary sequences of morphic and Sturmian words.
  82. On the Optimisation of the GSACA Suffix Array Construction Algorithm.
  83. On the Power of Learning-Augmented BSTs.
  84. On the Practical Power of Automata in Pattern Matching.
  85. Onesweep: A Faster Least Significant Digit Radix Sort for GPUs.
  86. Online List Labeling: Breaking the log2n Barrier.
  87. Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions.
  88. Optimal resizable arrays.
  89. Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.
  90. PalFM-index: FM-index for Palindrome Pattern Matching.
  91. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond.
  92. Pareto Optimal Compression of Genomic Dictionaries, with or without Random Access in Main Memory.
  93. Pattern matching algorithms in Blockchain for network fees reduction.
  94. Pattern matching under DTW distance.
  95. Polyominoes and graphs built from Fibonacci words.
  96. Practical KMP/BM Style Pattern-Matching on Indeterminate Strings.
  97. Prefix Filter: Practically and Theoretically Better Than Bloom.
  98. Prefix-free parsing for building large tunnelled Wheeler graphs.
  99. Properties of a Ternary Infinite Word.
  100. Pseudoperiodic Words and a Question of Shevelev.
  101. Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching.
  102. Quantum jumbled pattern matching.
  103. Reduction ratio of the IS-algorithm: worst and random cases.
  104. Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings.
  105. SicHash - Small Irregular Cuckoo Tables for Perfect Hashing.
  106. Simple O(1) Query Algorithm for Level Ancestors.
  107. Simpler and Better Cardinality Estimators for HyperLogLog and PCSA.
  108. Software-Hardware Codesign for Efficient In-Memory Regular Pattern Matching.
  109. Some Results on Digital Segments and Balanced Words.
  110. Sorting Genomes by Prefix Double-Cut-and-Joins.
  111. Space-Efficient STR-IC-LCS Computation.
  112. Space-efficient RLZ-to-LZ77 conversion.
  113. Space-efficient conversions from SLPs.
  114. Space-efficient data structure for next/previous larger/smaller value queries.
  115. Speeding Hirschberg Algorithm for Sequence Alignment.
  116. Splay Top Trees.
  117. String Attractors and Infinite Words.
  118. String Covering: A Survey.
  119. String Rearrangement Inequalities and a Total Order Between Primitive Words.
  120. Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems.
  121. Subsequences in Bounded Ranges: Matching and Analysis Problems.
  122. Substring Complexities on Run-length Compressed Strings.
  123. Suffix sorting via matching statistics.
  124. Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems.
  125. Taming Large-Scale Genomic Analyses via Sparsified Genomics.
  126. Teaching the Burrows-Wheeler Transform via the Positional Burrows-Wheeler Transform.
  127. The Complexity of the Co-Occurrence Problem.
  128. Theoretical analysis of edit distance algorithms: an applied perspective.
  129. Tight Bounds for Monotone Minimal Perfect Hashing.
  130. Transcoding Unicode Characters with AVX-512 Instructions.
  131. Trie-Compressed Intersectable Sets.
  132. Unbalancing Binary Trees.
  133. Walking on Words.
  134. Watson-Crick conjugates of words and languages.
  135. Which arithmetic operations can be performed in constant time in the RAM model with addition?
  136. Word Equations in Synergy with Regular Constraints (Technical Report).

Commun. ACM 2022

  1. Resolution of the burrows-wheeler transform conjecture.
  2. The compression power of the BWT: technical perspective.

IEEE Access 2022

  1. Compressing and Querying Integer Dictionaries Under Linearities and Repetitions.

Inf. Comput. 2022

  1. A periodicity lemma for partial words.
  2. Efficient representation and counting of antipower factors in words.
  3. LZRR: LZ77 parsing with right reference.
  4. Order-preserving pattern matching indeterminate strings.
  5. c-trie++: A dynamic trie tailored for fast prefix searches.

Inf. Process. Lett. 2022

  1. All-pairs suffix/prefix in optimal time using Aho-Corasick space.
  2. Palindromic trees for a sliding window and its applications.

Inf. Retr. J. 2022

  1. Applying burst-tries for error-tolerant prefix search.

J. Comput. Biol. 2022

  1. Finding Maximal Exact Matches Using the r-Index.
  2. MONI: A Pangenomic Index for Finding Maximal Exact Matches.

J. Comput. Sci. 2022

  1. A sorting algorithm based on ordered block insertions.

SN Comput. Sci. 2022

  1. Combining Forward Compression with PPM.
  2. Correction to: Graph Compression for Adjacency-Matrix Multiplication.
  3. Graph Compression for Adjacency-Matrix Multiplication.

Theor. Comput. Sci. 2022

  1. A data structure for substring-substring LCS length queries.
  2. An efficient algorithm for the longest common palindromic subsequence problem.
  3. Combinatorics of minimal absent words for a sliding window.
  4. Efficient and compact representations of some non-canonical prefix-free codes.
  5. In-place initializable arrays.
  6. Internal shortest absent word queries in constant time and linear space.
  7. Parameterized DAWGs: Efficient constructions and bidirectional pattern searches.
  8. Partial sums on the ultra-wide word RAM.

Theory Comput. Syst. 2022

  1. Factorizing Strings into Repetitions.
This site is open source. Improve this page.