StringologyTimes

Papers for stringologist (2024)

• ACIIDS (Companion 1)(2024) [dblp]
• CALDAM(2024) [dblp]
• EvoStar(2024) [dblp]
• FUN(2024) [dblp]
• GASCom(2024) [dblp]
• GandALF(2024) [dblp]
• ICCS (5)(2024) [dblp]
• IJTCS-FAW(2024) [dblp]

• TAMC(2024) [dblp]

• ACM Trans. Algorithms(2024) [dblp]
• Acta Informatica(2024) [dblp]
• Algorithmica(2024) [dblp]
• Algorithms(2024) [dblp]
• Bioinform.(2024) [dblp]
• CoRR(2024) [dblp]
• Comput. J.(2024) [dblp]
• Discret. Appl. Math.(2024) [dblp]
• Inf. Comput.(2024) [dblp]
• Inf. Syst.(2024) [dblp]
• J. Comb. Theory, Ser. A(2024) [dblp]
• J. Comput. Syst. Sci.(2024) [dblp]
• J. Supercomput.(2024) [dblp]
• Knowl. Based Syst.(2024) [dblp]
• SIAM J. Comput.(2024) [dblp]
• Theor. Comput. Sci.(2024) [dblp]
• Theory Comput. Syst.(2024) [dblp]
• VLDB J.(2024) [dblp]

Contents

ACIIDS (Companion 1) 2024

1. The Merged Longest Common Increasing Subsequence Problem.

CALDAM 2024

1. Consecutive Occurrences with Distance Constraints.

EvoStar 2024

1. A Neural Network Based Guidance for a BRKGA: An Application to the Longest Common Square Subsequence Problem.

FUN 2024

1. Baba Is Universal.
2. Snake in Optimal Space and Time.
3. The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples.

GASCom 2024

1. A Symmetry Property of Christoffel Words.
2. Perfectly Clustering Words and Iterated Palindromes over a Ternary Alphabet.

GandALF 2024

1. Deterministic Suffix-reading Automata.

ICCS (5) 2024

1. Efficient Search Algorithms for the Restricted Longest Common Subsequence Problem.

IJTCS-FAW 2024

1. [Longest (k]-Tuple Common Substrings.](https://doi.org/10.1007/978-981-97-7752-5_8)

TAMC 2024

1. Quantum Path Parallelism: A Circuit-Based Approach to Text Searching.

ACM Trans. Algorithms 2024

1. Generic Non-recursive Suffix Array Construction.

Acta Informatica 2024

1. Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm.
2. The longest letter-duplicated subsequence and related problems.

Algorithmica 2024

1. Pattern Masking for Dictionary Matching: Theory and Practice.

Algorithms 2024

1. Computing RF Tree Distance over Succinct Representations.
2. Text Indexing for Faster Gapped Pattern Matching.

Bioinform. 2024

1. Sigmoni: classification of nanopore signal with a compressed pangenome index.

CoRR 2024

1. A Connection Between Unbordered Partial Words and Sparse Rulers.
2. A Family of LZ78-based Universal Sequential Probability Assignments.
3. A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities.
4. A Lock-free Binary Trie.
5. A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation.
6. A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs.
7. A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm.
8. A simpler data structure for dynamic strings.
9. A visualization tool to explore alphabet orderings for the Burrows-Wheeler Transform.
10. Adaptive Dynamic Bitvectors.
11. Algorithms for Galois Words: Detection, Factorization, and Rotation.
12. Algorithms for Parameterized String Matching with Mismatches.
13. All-Pairs Suffix-Prefix on Dynamic Set of Strings.
14. Almost Linear Size Edit Distance Sketch.
15. An 11/6-Approximation Algorithm for Vertex Cover on String Graphs.
16. An Algorithm for a Modification of the Shortest Common Superstring Problem.
17. An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings.
18. An Implementation and Experimental Comparison of Dynamic Ordered Sets.
19. An Optimal Algorithm for Sorting Pattern-Avoiding Sequences.
20. Approximate Circular Pattern Matching under Edit Distance.
21. Avoiding abelian and additive powers in rich words.
22. BAT-LZ Out of Hell.
23. Better space-time-robustness trade-offs for set reconciliation.
24. Bijective BWT based compression schemes.
25. Bit catastrophes for the Burrows-Wheeler Transform.
26. Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights.
27. Characterization of Isometric Words based on Swap and Mismatch Distance.
28. Characterizing and Transforming DAGs within the I-LCA Framework.
29. Christoffel Matrices and Sturmian Determinants.
30. Closed Repeats.
31. Combinatorics on words and generating Dirichlet series of automatic sequences.
32. Comparative genomics with succinct colored de Bruijn graphs.
33. Compressed Game Solving.
34. Compression with wildcards: All induced metric subgraphs.
35. Computing Longest Common Subsequence under Cartesian-Tree Matching Model.
36. Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space.
37. Computing String Covers in Sublinear Time.
38. Computing the LCP Array of a Labeled Graph.
39. Computing the LZ-End parsing: Easy to implement and practically efficient.
40. Computing the k-binomial complexity of generalized Thue-Morse words.
41. Consecutive Power Occurrences in Sturmian Words.
42. Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications.
43. Counting on General Run-Length Grammars.
44. Counting overlapping pairs of strings.
45. Differentially Private Substring and Document Counting.
46. Dudeney’s Dissection is Optimal.
47. Dynamic Range Minimum Queries on the Ultra-Wide Word RAM.
48. Dynamic Suffix Array in Optimal Compressed Space.
49. Edit and Alphabet-Ordering Sensitivity of Lex-parse.
50. Efficient Construction of Long Orientable Sequences.
51. Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences.
52. Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing.
53. Efficient top-down updates in AVL trees.
54. Elastic-Degenerate String Comparison.
55. Enhanced Graph Pattern Matching.
56. Enumeration for MSO-Queries on Compressed Trees.
57. Evaluating n-Gram Novelty of Language Models Using Rusty-DAWG.
58. Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs.
59. Exploiting New Properties of String Net Frequency for Efficient Computation.
60. Exploring Repetitiveness Measures for Two-Dimensional Strings.
61. Exploring the Crochemore and Ziv-Lempel factorizations of some automatic sequences with the software Walnut.
62. Exponent-Strings and Their Edit Distance.
63. Extending the Burrows-Wheeler Transform for Cartesian Tree Matching and Constructing It.
64. Fast and Lightweight Distributed Suffix Array Construction - First Results.
65. Fast and Simple Sorting Using Partial Information.
66. Fast and Small Subsampled R-indexes.
67. Fast computation of the period and of the shortest cover of a string using its Character-Distance-Sampling representation.
68. Faster and Simpler Online Computation of String Net Frequency.
69. Faster and simpler online/sliding rightmost Lempel-Ziv factorizations.
70. Faster two-dimensional pattern matching with k mismatches.
71. Fault-Equivalent Lowest Common Ancestors.
72. Finding Diverse Strings and Longest Common Subsequences in a Graph.
73. From the Lyndon factorization to the Canonical Inverse Lyndon factorization: back and forth.
74. Generalized Straight-Line Programs.
75. Greedy Conjecture for the Shortest Common Superstring Problem and its Strengthenings.
76. Hairpin Completion Distance Lower Bound.
77. Hardness Amplification for Dynamic Binary Search Trees.
78. Hardness Results on Characteristics for Elastic-Degenerated Strings.
79. Height-bounded Lempel-Ziv encodings.
80. Heuristics for the Run-length Encoded Burrows-Wheeler Transform Alphabet Ordering Problem.
81. How to Find Long Maximal Exact Matches and Ignore Short Ones.
82. Implementation Of Dynamic De Bruijn Graphs Via Learned Index.
83. Improved Lower Bounds on the Expected Length of Longest Common Subsequences.
84. Incremental computation of the set of period sets.
85. Indexing Finite-State Automata Using Forward-Stable Partitions.
86. Internal Pattern Matching in Small Space and Applications.
87. Iterated Straight-Line Programs.
88. Kolmogorov complexity as a combinatorial tool.
89. Lempel-Ziv (LZ77) Factorization in Sublinear Time.
90. Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees.
91. Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved.
92. Lock-Free Augmented Trees.
93. Longest Common Extensions with Wildcards: Trade-off and Applications.
94. Lyndon pairs and the lexicographically greatest perfect necklace.
95. MIOV: Reordering MOVI for even better locality.
96. Many Flavors of Edit Distance.
97. Maximal number of subword occurrences in a word.
98. Minimizing the Minimizers via Alphabet Reordering.
99. Movelet Trees.
100. NP-Completeness for the Space-Optimality of Double-Array Tries.
101. Near-Optimal Trace Reconstruction for Mildly Separated Strings.
102. Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching.
103. New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching.
104. New Compressed Indices for Multijoins on Graph Databases.
105. On Computing the Smallest Suffixient Set.
106. On Differentially Private String Distances.
107. On multidimensional generalization of binary search.
108. On the Communication Complexity of Approximate Pattern Matching.
109. On the Complexity of Computing the Co-lexicographic Width of a Regular Language.
110. On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms.
111. On the Number of Non-equivalent Parameterized Squares in a String.
112. On the complexity and approximability of Bounded access Lempel Ziv coding.
113. On the compressiveness of the Burrows-Wheeler transform.
114. On the longest increasing subsequence and number of cycles of butterfly permutations.
115. On the number of k-mers admitting a given lexicographical minimizer.
116. On the piecewise complexity of words.
117. Online Computation of String Net Frequency.
118. Online String Attractors.
119. Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees.
120. Optimal Bounds for Distinct Quartics.
121. Optimal Static Dictionary with Worst-Case Constant Query Time.
122. Optimal prefix-suffix queries with applications.
123. Packed Acyclic Deterministic Finite Automata.
124. Palindromes Compression and Retrieval.
125. Palindromic length of infinite aperiodic words.
126. Pattern Matching with Mismatches and Wildcards.
127. QR Sort: A Novel Non-Comparative Sorting Algorithm.
128. Quantum Algorithm for the Multiple String Matching Problem.
129. Quantum search in a dictionary based on fingerprinting-hashing.
130. Range Longest Increasing Subsequence and its Relatives: Beating Quadratic Barrier and Approaching Optimality.
131. Recovery of cyclic words by their subwords.
132. Regular Languages in the Sliding Window Model.
133. Relating Left and Right Extensions of Maximal Repeats.
134. Relative position in binary substitutions.
135. Repetition Threshold for Binary Automatic Sequences.
136. Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration.
137. Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings.
138. Rollercoasters with Plateaus.
139. Runs in Paperfolding Sequences.
140. SPIDER: Improved Succinct Rank and Select Performance.
141. Scalable Distributed String Sorting.
142. Scalable Order-Preserving Pattern Mining.
143. ShiftDTW: adapting the DTW metric for cyclic time series clustering.
144. Shortest cover after edit.
145. Simple Linear-time Repetition Factorization.
146. Simplified Tight Bounds for Monotone Minimal Perfect Hashing.
147. Small Space Encoding and Recognition of k-Palindromic Prefixes.
148. Some Remarks on Palindromic Periodicities.
149. Sorted Consecutive Occurrence Queries in Substrings.
150. Space-Efficient Indexes for Uncertain Strings.
151. Space-Efficient Online Computation of String Net Occurrences.
152. Space-efficient SLP Encoding for O(log N)-time Random Access.
153. Stability properties for subgroups generated by return words.
154. String 2-Covers with No Length Restrictions.
155. String Partition for Building Big BWTs.
156. String attractors and bi-infinite words.
157. Subsequence Matching and Analysis Problems for Formal Languages.
158. Subsequence Pattern Matching with Segment Number Constraint.
159. Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds.
160. Substring Compression Variations and LZ78-Derivates.
161. Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage.
162. Succinct Data Structures for Segments.
163. Tag arrays.
164. Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests.
165. Text Indexing for Long Patterns using Locally Consistent Anchors.
166. The CDAWG Index and Pattern Matching on Grammar-Compressed Strings.
167. The Quasi-probability Method and Applications for Trace Reconstruction.
168. The Repetition Threshold for Rote Sequences.
169. The Shortest Interesting Binary Words.
170. The reflection complexity of sequences over finite alphabets.
171. The repetition threshold for ternary rich words.
172. Theoretical Analysis of Byte-Pair Encoding.
173. Theoretical insights and an experimental comparison of tango trees and multi-splay trees.
174. Tight Bounds for the Number of Absent Scattered Factors.
175. Top-k Stabbing Interval Queries.
176. Toward Greener Matrix Operations by Lossless Compressed Formats.
177. Towards Optimal Grammars for RNA Structures.
178. TwinArray Sort: An Ultrarapid Conditional Non-Comparison Based Sorting Algorithm.
179. Unveiling the connection between the Lyndon factorization and the Canonical Inverse Lyndon factorization via a border property.
180. Upper Bounds for Complexity of Asymptotically Optimal Learned Indexes.
181. Upper bounds on the average edit distance between two random strings.
182. Utilizing ChatGPT in a Data Structures and Algorithms Course: A Teaching Assistant’s Perspective.
183. V-Words, Lyndon Words and Galois Words.
184. Word equations, constraints, and formal languages.

Comput. J. 2024

1. Dynamic compact data structure for temporal reachability with unsorted contact insertions.

Discret. Appl. Math. 2024

1. On arithmetically progressed suffix arrays and related Burrows-Wheeler transforms.
2. Polynomial-time equivalences and refined algorithms for longest common subsequence variants.

Inf. Comput. 2024

1. Constructing and indexing the bijective and extended Burrows-Wheeler transform.

Inf. Syst. 2024

1. CoCo-trie: Data-aware compression and indexing of strings.

J. Comb. Theory, Ser. A 2024

1. New string attractor-based complexities for infinite words.

J. Comput. Syst. Sci. 2024

1. The tree-child network inference problem for line trees and the shortest common supersequence problem for permutation strings.

J. Supercomput. 2024

1. Palindromes in involutive Fibonacci arrays.

Knowl. Based Syst. 2024

1. Dynamic-MLCS: Fast searching for dynamic multiple longest common subsequences in sequence stream data.

SIAM J. Comput. 2024

1. Internal Pattern Matching Queries in a Text and Applications.

Theor. Comput. Sci. 2024

1. Faster space-efficient STR-IC-LCS computation.

Theory Comput. Syst. 2024

1. Elastic-Degenerate String Matching with 1 Error or Mismatch.
2. String Attractors of Some Simple-Parry Automatic Sequences.

VLDB J. 2024

1. Optimizing RPQs over a compact graph representation.

This site is open source. Improve this page.