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]
• SPIRE(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]
• 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]
• 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. Front Matter, Table of Contents, Preface, Conference Organization.
10. Improving the Sensitivity of MinHash Through Hash-Value Analysis.
11. L-Systems for Measuring Repetitiveness.
12. Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String.
13. MONI Can Find k-MEMs.
14. MUL-Tree Pruning for Consistency and Compatibility.
15. Merging Sorted Lists of Similar Strings.
16. On Distances Between Words with Parameters.
17. On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem.
18. On the Impact of Morphisms on BWT-Runs.
19. Optimal LZ-End Parsing Is Hard.
20. Optimal Near-Linear Space Heaviest Induced Ancestors.
21. Order-Preserving Squares in Strings.
22. PalFM-Index: FM-Index for Palindrome Pattern Matching.
23. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond.
24. Sliding Window String Indexing in Streams.
25. String Factorization via Prefix Free Families.
26. Suffix-Prefix Queries on a Dictionary.
27. 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.

SPIRE 2023

1. A Simple Grammar-Based Index for Finding Approximately Longest Common Substrings.
2. Algorithms and Hardness for the Longest Common Subsequence of Three Strings and Related Problems.
3. Approximate Cartesian Tree Matching: An Approach Using Swaps.
4. Approximation and Fixed Parameter Algorithms for the Approximate Cover Problem.
5. Binary Mixed-Digit Data Compression Codes.
6. CAGE: Cache-Aware Graphlet Enumeration.
7. Chaining of Maximal Exact Matches in Graphs.
8. Compacting Massive Public Transport Data.
9. Compressibility Measures for Two-Dimensional Data.
10. Computing All-vs-All MEMs in Grammar-Compressed Text.
11. Constant Time and Space Updates for the Sigma-Tau Problem.
12. Count-Min Sketch with Variable Number of Hash Functions: An Experimental Study.
13. Data Structures for SMEM-Finding in the PBWT.
14. Dynamic Compact Planar Embeddings.
15. Efficient Parameterized Pattern Matching in Sublinear Space.
16. Engineering a Textbook Approach to Index Massive String Dictionaries.
17. Evaluating Regular Path Queries on Compressed Adjacency Matrices.
18. Frequency-Constrained Substring Complexity.
19. From de Bruijn Graphs to Variation Graphs - Relationships Between Pangenome Models.
20. Largest Repetition Factorization of Fibonacci Words.
21. Linear-Time Computation of Generalized Minimal Absent Words for Multiple Strings.
22. Longest Common Prefix Arrays for Succinct k-Spectra.
23. New Advances in Rightmost Lempel-Ziv.
24. Non-overlapping Indexing in BWT-Runs Bounded Space.
25. On Suffix Tree Detection.
26. On the Number of Factors in the LZ-End Factorization.
27. Optimal Wheeler Language Recognition.
28. Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph.
29. Space-Time Trade-Offs for the LCP Array of Wheeler DFAs.
30. String Covers of a Tree Revisited.
31. Sublinear Time Lempel-Ziv (LZ77) Factorization.

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.

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.

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.