StringologyTimes

Papers for stringologist (2023)

• ALENEX(2023) [dblp]
• COCOA (1)(2023) [dblp]
• COCOA (2)(2023) [dblp]
• CPM(2023) [dblp]
• DCC(2023) [dblp]
• DLT(2023) [dblp]
• ISBRA(2023) [dblp]
• ITCS(2023) [dblp]
• SISAP(2023) [dblp]
• SODA(2023) [dblp]
• SOFSEM(2023) [dblp]
• SOSA(2023) [dblp]
• STACS(2023) [dblp]
• STOC(2023) [dblp]
• WALCOM(2023) [dblp]

• WORDS(2023) [dblp]

• ACM Trans. Algorithms(2023) [dblp]
• Algorithmica(2023) [dblp]
• Bioinform.(2023) [dblp]
• CoRR(2023) [dblp]
• Comput. Sci. Rev.(2023) [dblp]
• IEEE Trans. Commun.(2023) [dblp]
• IEEE Trans. Inf. Theory(2023) [dblp]
• IEEE Trans. Knowl. Data Eng.(2023) [dblp]
• Inf. Comput.(2023) [dblp]
• Inf. Process. Lett.(2023) [dblp]
• Int. J. Comput. Geom. Appl.(2023) [dblp]
• J. Comput. Biol.(2023) [dblp]
• Multim. Tools Appl.(2023) [dblp]
• Proc. VLDB Endow.(2023) [dblp]
• Theor. Comput. Sci.(2023) [dblp]

Contents

ALENEX 2023

1. LZ77 via Prefix-Free Parsing.
2. Lower Bounds for Sorting 16, 17, and 18 Elements.
3. Multiway Powersort.
4. PaCHash: Packed and Compressed Hash Tables.
5. SicHash - Small Irregular Cuckoo Tables for Perfect Hashing.

COCOA (1) 2023

1. V-Words, Lyndon Words and Substring circ-UMFFs.

COCOA (2) 2023

1. On Problems Related to Absent Subsequences.

CPM 2023

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

DCC 2023

1. Augmented Thresholds for MONI.
2. Bit-Parallel (Compressed) Wavelet Tree Construction.
3. Computing matching statistics on Wheeler DFAs.
4. Computing the optimal BWT of very large string collections.
5. Constructing the CDAWG CFG using LCP-Intervals.
6. Contextual Pattern Matching in Less Space.
7. FM-Directories: Extending the Burrows-Wheeler Transform for String Labeled Vertex Graphs of (Almost) Arbitrary Topology.
8. JARVIS2: a data compressor for large genome sequences.
9. LZ4r - A New Fast Compression Algorithm for High-Speed Data Storage Systems.
10. Measuring the Similarity of Files by Data Compression.
11. Model Compression for Data Compression: Neural Network Based Lossless Compressor Made Practical.
12. Permutation coding using divide-and-conquer strategy.
13. Practical Implementations of Compressed RAM.
14. RNA secondary structures: from ab initio prediction to better compression, and back.
15. Recursive Prefix-Free Parsing for Building Big BWTs.
16. SnappyR: A New High-Speed Lossless Data Compression Algorithm.

DLT 2023

1. Bit Catastrophes for the Burrows-Wheeler Transform.

ISBRA 2023

1. CSA-MEM: Enhancing Circular DNA Multiple Alignment Through Text Indexing Algorithms.

ITCS 2023

1. An Algorithmic Bridge Between Hamming and Levenshtein Distances.

SISAP 2023

1. Runs of Side-Sharing Tandems in Rectangular Arrays.

SODA 2023

1. 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time.
2. A Nearly-Tight Analysis of Multipass Pairing Heaps.
3. A Tight Analysis of Slim Heaps and Smooth Heaps.
4. Breaking the 𝒪(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees.
5. Optimal Square Detection Over General Alphabets.
6. Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching.
7. Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.
8. Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures.
9. Tight Bounds for Monotone Minimal Perfect Hashing.
10. Tiny Pointers.

SOFSEM 2023

1. Space-Efficient STR-IC-LCS Computation.
2. The k-Centre Problem for Classes of Cyclic Words.

SOSA 2023

1. An Optimal Lower Bound for Simplex Range Reporting.
2. Optimal resizable arrays.
3. Splay Top Trees.

STACS 2023

1. Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm.
2. Dynamic Data Structures for Parameterized String Problems.
3. Real Numbers Equally Compressible in Every Base.
4. Reconstructing Words Using Queries on Subwords or Factors.

STOC 2023

1. Approximating Binary Longest Common Subsequence in Almost-Linear Time.
2. External Memory Fully Persistent Search Trees.
3. Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching.
4. Weighted Edit Distance Computation: Strings, Trees, and Dyck.

WALCOM 2023

1. Efficient Non-isomorphic Graph Enumeration Algorithms for Subclasses of Perfect Graphs.
2. Energy Efficient Sorting, Selection and Searching.
3. Finding the Cyclic Covers of a String.
4. Inferring Strings from Position Heaps in Linear Time.
5. Internal Longest Palindrome Queries in Optimal Time.
6. Parity Permutation Pattern Matching.

WORDS 2023

1. Smallest and Largest Block Palindrome Factorizations.
2. String Attractors for Factors of the Thue-Morse Word.
3. String Attractors of Fixed Points of k-Bonacci-Like Morphisms.

ACM Trans. Algorithms 2023

1. On the Complexity of String Matching for Graphs.

Algorithmica 2023

1. Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series.

Bioinform. 2023

1. μ- PBWT: a lightweight r-indexing of the PBWT for storing and querying UK Biobank data.

CoRR 2023

1. (min, +) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences.
2. A Compact DAG for Storing and Searching Maximal Common Subsequences.
3. A Compact Representation for AVL Trees.
4. A Huffman based short message service compression technique using adjacent distance array.
5. A Myhill-Nerode Theorem for Generalized Automata.
6. A Simple Data Structure for Maintaining a Discrete Probability Distribution.
7. A symbolic-arithmetic for teaching double-black node removal in red-black trees.
8. Acceleration of FM-index Queries Through Prefix-free Parsing.
9. Adaptive Encoding Strategies for Erasing-Based Lossless Floating-Point Compression.
10. Algorithms for Massive Data - Lecture Notes.
11. An Algorithm for the Constrained Longest Common Subsequence and Substring Problem.
12. An Algorithm for the Longest Common Subsequence and Substring Problem.
13. An Efficient B-tree Implementation for Memory-Constrained Embedded Systems.
14. Another virtue of wavelet forests?
15. Approximate Cartesian Tree Matching: an Approach Using Swaps.
16. Approximating Edit Distance in the Fully Dynamic Model.
17. B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.
18. Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching.
19. CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions.
20. Can You Solve Closest String Faster than Exhaustive Search?
21. Chaining of Maximal Exact Matches in Graphs.
22. Change a Bit to save Bytes: Compression for Floating Point Time-Series Data.
23. Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space.
24. Compressed Indexing for Consecutive Occurrences.
25. Compressibility measures for two-dimensional data.
26. Compressibility-Aware Quantum Algorithms on Strings.
27. Computing SEQ-IC-LCS of Labeled Graphs.
28. Computing all-vs-all MEMs in grammar-compressed text.
29. Computing matching statistics on Wheeler DFAs.
30. Counting occurrences of patterns in permutations.
31. Critical exponent of binary words with few distinct palindromes.
32. Deterministic 3SUM-Hardness.
33. Dyck Words, Pattern Avoidance, and Automatic Sequences.
34. Dynamic “Succincter”.
35. Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm.
36. Dynamic Compact Data Structure for Temporal Reachability with Unsorted Contact Insertions.
37. Dynamic Dictionary with Subconstant Wasted Bits per Key.
38. Dynamic Dynamic Time Warping.
39. Efficient Online String Matching through Linked Weak Factors.
40. Efficient Parallel Output-Sensitive Edit Distance.
41. Efficient Parameterized Pattern Matching in Sublinear Space.
42. Efficient algorithms for enumerating maximal common subsequences of two strings.
43. Engineering Rank/Select Data Structures for Big-Alphabet Strings.
44. Enumerating all minimal hitting sets in polynomial total time.
45. Erasing-based lossless compression method for streaming floating-point time series.
46. Evaluating Regular Path Queries on Compressed Adjacency Matrices.
47. Exact Shortest Paths with Rational Weights on the Word RAM.
48. Fast and simple unrooted dynamic forests.
49. Fast computation of approximate weak common intervals in multiple indeterminate strings.
50. Faster Algorithms for Internal Dictionary Queries.
51. Faster Algorithms for Text-to-Pattern Hamming Distances.
52. Faster Compression of Deterministic Finite Automata.
53. Faster Maximal Exact Matches with Lazy LCP Evaluation.
54. Faster Prefix-Sorting Algorithms for Deterministic Finite Automata.
55. Faster Wavelet Trees with Quad Vectors.
56. Finding Maximal Exact Matches in Graphs.
57. Finding a reconfiguration sequence between longest increasing subsequences.
58. Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data.
59. Hierarchical Lowrank Arithmetic with Binary Compression.
60. Learned Monotone Minimal Perfect Hashing.
61. Linear Time Construction of Cover Suffix Tree and Applications.
62. Linear Time Online Algorithms for Constructing Linear-size Suffix Trie.
63. Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets.
64. Linear-time computation of generalized minimal absent words for multiple strings.
65. Locally consistent decomposition of strings with applications to edit distance sketching.
66. Longest Common Prefix Arrays for Succinct k-Spectra.
67. Longest Common Subsequence with Gap Constraints.
68. Longest Common Substring and Longest Palindromic Substring in Õ(√n) Time.
69. Lossy Compressor preserving variant calling through Extended BWT.
70. Maintaining the cycle structure of dynamic permutations.
71. Matching Patterns with Variables Under Simon’s Congruence.
72. Matching Statistics speed up BWT construction.
73. Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings.
74. Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization.
75. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
76. On Sensitivity of Compact Directed Acyclic Word Graphs.
77. On arch factorization and subword universality for words and compressed words.
78. On the Maximal Independent Sets of k-mers with the Edit Distance.
79. On the k-Hamming and k-Edit Distances.
80. On the piecewise complexity of words and periodic words.
81. Optimal Algorithms for Bounded Weighted Edit Distance.
82. Optimal Heaviest Induced Ancestors.
83. Optimal LZ-End Parsing is Hard.
84. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing.
85. Optimal Square Detection Over General Alphabets.
86. Optimal Wheeler Language Recognition.
87. Optimal-Hash Exact String Matching Algorithms.
88. Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph.
89. Optimization with pattern-avoiding input.
90. Order-Preserving Squares in Strings.
91. Pairwise sequence alignment with block and character edit operations.
92. Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions.
93. Pb-Hash: Partitioned b-bit Hashing.
94. Phylogenetic tree distance computation over succinct representations.
95. Prefix Sorting DFAs: a Recursive Algorithm.
96. Prefix-free graphs and suffix array construction in sublinear space.
97. Prefixes of the Fibonacci word.
98. Quantum Circuits for Fixed Substring Matching Problems.
99. Random Wheeler Automata.
100. Range Entropy Queries and Partitioning.
101. Rank and Select on Degenerate Strings.
102. Ranking and Unranking k-subsequence universal words.
103. Ranking and unranking bordered and unbordered words.
104. Reconstructing words using queries on subwords or factors.
105. Repetition factorization of automatic sequences.
106. Rudin-Shapiro Sums Via Automata Theory and Logic.
107. Searching 2D-Strings for Matching Frames.
108. SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree.
109. Selective Run-Length Encoding.
110. Shorter and faster than Sort3AlphaDev.
111. Size-constrained Weighted Ancestors with Applications.
112. Sketching and Streaming for Dictionary Compression.
113. Sliding Window String Indexing in Streams.
114. Sliding suffix trees simplified.
115. Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares.
116. Smallest and Largest Block Palindrome Factorizations.
117. Some Fibonacci-Related Sequences.
118. Sorting Finite Automata via Partition Refinement.
119. Space-Efficient Data Structures for Polyominoes and Bar Graphs.
120. Space-time Trade-offs for the LCP Array of Wheeler DFAs.
121. Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast.
122. Storing a Trie with Compact and Predictable Space.
123. Streaming k-edit approximate pattern matching via string decomposition.
124. String attractors of fixed points of k-bonacci-like morphisms.
125. Structure and growth of R-bonacci words.
126. Sturmian and infinitely desubstitutable words accepted by an ω-automaton.
127. Subcubic algorithm for (Unweighted) Unrooted Tree Edit Distance.
128. Succinct Data Structure for Graphs with d-Dimensional t-Representation.
129. Succinct Planar Encoding with Minor Operations.
130. Suffixient Sets.
131. Sum-of-Local-Effects Data Structures for Separable Graphs.
132. The 2-Attractor Problem is NP-Complete.
133. The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing.
134. The Lexicographically Least Binary Rich Word Achieving the Repetition Threshold.
135. The Longest Subsequence-Repeated Subsequence Problem.
136. The Many Qualities of a New Directly Accessible Compression Scheme.
137. The analogue of overlap-freeness for the Fibonacci morphism.
138. The analogue of overlap-freeness for the period-doubling sequence.
139. Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries.
140. Two-dimensional Dyck words.
141. Weighted Edit Distance Computation: Strings, Trees and Dyck.
142. Wheeler maps.

Comput. Sci. Rev. 2023

1. Abelian combinatorics on words: A survey.

IEEE Trans. Commun. 2023

1. Reconstruction of Sets of Strings From Prefix/Suffix Compositions.

IEEE Trans. Inf. Theory 2023

1. Toward a Definitive Compressibility Measure for Repetitive Sequences.

IEEE Trans. Knowl. Data Eng. 2023

1. Bidirectional String Anchors for Improved Text Indexing and Top-$K$ Similarity Search.

Inf. Comput. 2023

1. Compact representations of spatial hierarchical structures with support for topological queries.
2. Sensitivity of string compressors and repetitiveness measures.

Inf. Process. Lett. 2023

1. Longest bordered and periodic subsequences.
2. Order-preserving pattern matching with scaling.
3. Space-efficient Huffman codes revisited.

Int. J. Comput. Geom. Appl. 2023

1. Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries.

J. Comput. Biol. 2023

1. Efficient Colored de Bruijn Graph for Indexing Reads.

Multim. Tools Appl. 2023

1. Scalable thread based index construction using wavelet tree.

Proc. VLDB Endow. 2023

1. Text Indexing for Long Patterns: Anchors are All you Need.

Theor. Comput. Sci. 2023

1. Compact suffix automata representations for searching long patterns.
2. Improved characters distance sampling for online and offline text searching.
3. Linear-space S-table algorithms for the longest common subsequence problem.
4. Maximal degenerate palindromes with gaps and mismatches.

This site is open source. Improve this page.