StringologyTimes

Papers for stringologist (2020)

• ALENEX(2020) [dblp]
• APPROX-RANDOM(2020) [dblp]
• BCB(2020) [dblp]
• CPM(2020) [dblp]
• CSR(2020) [dblp]
• CiE(2020) [dblp]
• DCC(2020) [dblp]
• DLT(2020) [dblp]
• ESA(2020) [dblp]
• Euro-Par(2020) [dblp]
• FOCS(2020) [dblp]
• FSTTCS(2020) [dblp]
• ICALP(2020) [dblp]
• ICDT(2020) [dblp]
• ISAAC(2020) [dblp]
• ITCS(2020) [dblp]
• IWOCA(2020) [dblp]
• LATA(2020) [dblp]
• LATIN(2020) [dblp]
• SEA(2020) [dblp]
• SODA(2020) [dblp]
• SOFSEM(2020) [dblp]
• SOSA(2020) [dblp]
• SPIRE(2020) [dblp]
• STACS(2020) [dblp]
• STOC(2020) [dblp]
• SWAT(2020) [dblp]
• SoCG(2020) [dblp]
• TAMC(2020) [dblp]
• WABI(2020) [dblp]

• WALCOM(2020) [dblp]

• ACM J. Exp. Algorithmics(2020) [dblp]
• ACM Trans. Algorithms(2020) [dblp]
• Algorithmica(2020) [dblp]
• Algorithms(2020) [dblp]
• Algorithms Mol. Biol.(2020) [dblp]
• BMC Bioinform.(2020) [dblp]
• Bioinform.(2020) [dblp]
• Discret. Appl. Math.(2020) [dblp]
• Fundam. Informaticae(2020) [dblp]
• Inf.(2020) [dblp]
• Inf. Comput.(2020) [dblp]
• Int. J. Found. Comput. Sci.(2020) [dblp]
• J. ACM(2020) [dblp]
• J. Comput. Biol.(2020) [dblp]
• J. Signal Process. Syst.(2020) [dblp]
• Proc. VLDB Endow.(2020) [dblp]
• Theor. Comput. Sci.(2020) [dblp]
• Theory Comput. Syst.(2020) [dblp]

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. Genomic Problems Involving Copy Number Profiles: Complexity and Algorithms.
16. In-Place Bijective Burrows-Wheeler Transforms.
17. Longest Common Subsequence on Weighted Sequences.
18. On Extensions of Maximal Repeats in Compressed Strings.
19. On Indeterminate Strings Matching.
20. On Two Measures of Distance Between Fully-Labelled Trees.
21. Parameterized Algorithms for Matrix Completion with Radius Constraints.
22. String Factorizations Under Various Collision Constraints.
23. String Sanitization Under Edit Distance.
24. Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions.
25. Text Indexing and Searching in Sublinear Time.
26. The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time.
27. Time-Space Tradeoffs for Finding a Long Common Substring.
28. Unary Words Have the Smallest Levenshtein k-Neighbourhoods.
29. 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.

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.

Discret. Appl. Math. 2020

1. Accelerated partial decoding in wavelet trees.
2. Dynamic index and LZ factorization in compressed space.

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.