StringologyTimes

Papers for stringologist (2019)

• ALENEX(2019) [dblp]
• CIAC(2019) [dblp]
• CIKM(2019) [dblp]
• CPM(2019) [dblp]
• DCC(2019) [dblp]
• DEXA (2)(2019) [dblp]
• DLT(2019) [dblp]
• ECML/PKDD (1)(2019) [dblp]
• ESA(2019) [dblp]
• FCT(2019) [dblp]
• FOCS(2019) [dblp]
• ICALP(2019) [dblp]
• INNSBDDL (Tutorials)(2019) [dblp]
• ISAAC(2019) [dblp]
• ITCS(2019) [dblp]
• IWOCA(2019) [dblp]
• LATA(2019) [dblp]
• MFCS(2019) [dblp]
• RECOMB(2019) [dblp]
• SEA²(2019) [dblp]
• SODA(2019) [dblp]
• SOFSEM(2019) [dblp]
• SPIRE(2019) [dblp]
• STACS(2019) [dblp]
• STOC(2019) [dblp]
• WABI(2019) [dblp]
• WADS(2019) [dblp]
• WALCOM(2019) [dblp]

• WORDS(2019) [dblp]

• ACM J. Exp. Algorithmics(2019) [dblp]
• ACM Trans. Algorithms(2019) [dblp]
• ACM Trans. Inf. Syst.(2019) [dblp]
• Algorithmica(2019) [dblp]
• Algorithms(2019) [dblp]
• Algorithms Mol. Biol.(2019) [dblp]
• Bioinform.(2019) [dblp]
• Comput. J.(2019) [dblp]
• Dagstuhl Reports(2019) [dblp]
• IEEE Trans. Inf. Theory(2019) [dblp]
• Inf. Comput.(2019) [dblp]
• Inf. Process. Lett.(2019) [dblp]
• Inf. Sci.(2019) [dblp]
• Inf. Syst.(2019) [dblp]
• J. Comb. Optim.(2019) [dblp]
• J. Comput. Syst. Sci.(2019) [dblp]
• Rev. Socionetwork Strateg.(2019) [dblp]
• SIAM J. Comput.(2019) [dblp]
• SIAM J. Discret. Math.(2019) [dblp]
• Softw. Pract. Exp.(2019) [dblp]
• Theor. Comput. Sci.(2019) [dblp]
• Theory Comput. Syst.(2019) [dblp]

Contents

ALENEX 2019

1. Lightweight Distributed Suffix Array Construction.

CIAC 2019

1. The Parameterized Position Heap of a Trie.

CIKM 2019

1. Improved Compressed String Dictionaries.

CPM 2019

1. A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem.
2. A New Class of Searchable and Provably Highly Compressible String Transformations.
3. A Rearrangement Distance for Fully-Labelled Trees.
4. Approximating Approximate Pattern Matching.
5. Cartesian Tree Matching and Indexing.
6. Compressed Multiple Pattern Matching.
7. Computing Runs on a Trie.
8. Computing the Antiperiod(s) of a String.
9. Conversion from RLBWT to LZ77.
10. Dichotomic Selection on Words: A Probabilistic Analysis.
11. Entropy Lower Bounds for Dictionary Compression.
12. Faster Queries for Longest Substring Palindrome After Block Edit.
13. Finding a Small Number of Colourful Components.
14. Fully-Functional Bidirectional Burrows-Wheeler Indexes and Infinite-Order De Bruijn Graphs.
15. Hamming Distance Completeness.
16. How to Exploit Periodicity (Invited Talk).
17. Indexing the Bijective BWT.
18. Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding.
19. On Maximal Repeats in Compressed Strings.
20. On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations.
21. Online Algorithms for Constructing Linear-Size Suffix Trie.
22. Optimal Rank and Select Queries on Dictionary-Compressed Text.
23. Quasi-Linear-Time Algorithm for Longest Common Circular Factor.
24. Quasi-Periodicity in Streams.
25. Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding.
26. Searching Long Repeats in Streams.
27. Simulating the DNA Overlap Graph in Succinct Space.
28. Some Variations on Lyndon Words (Invited Talk).
29. Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform.
30. Streaming Dictionary Matching with Mismatches.
31. Stringology Combats Microbiological Threats (Invited Talk).
32. Sufficient Conditions for Efficient Indexing Under Different Matchings.

DCC 2019

1. A Compact Representation of Raster Time Series.
2. A New Technique for Lossless Compression of Color Images Based on Hierarchical Prediction, Inversion and Context Adaptive Coding.
3. BWT Tunnel Planning is Hard But Manageable.
4. Better Than Optimal Huffman Coding?
5. Constructing Antidictionaries in Output-Sensitive Space.
6. Dv2v: A Dynamic Variable-to-Variable Compressor.
7. Generalized Word Equations: A New Approach to Data Compresion.
8. LZRR: LZ77 Parsing with Right Reference.
9. Light Field Image Compression with Random Access.
10. MR-RePair: Grammar Compression Based on Maximal Repeats.
11. Multidimensional Compression with Pattern Matching.
12. Numerical Pattern Mining Through Compression.
13. On Lempel-Ziv Decompression in Small Space.
14. On the Randomness of Compressed Data.
15. Parameterized Text Indexing with One Wildcard.
16. Practical Indexing of Repetitive Collections Using Relative Lempel-Ziv.
17. RePair in Compressed Space and Time.
18. Regular Expression Search on Compressed Text.
19. Selective Dynamic Compression.
20. Space-Efficient Computation of the Burrows-Wheeler Transform.
21. Tunneling on Wheeler Graphs.
22. Vectorizing Fast Compression.

DEXA (2) 2019

1. Succinct BWT-Based Sequence Prediction.

DLT 2019

1. Computing the k-binomial Complexity of the Thue-Morse Word.
2. First Lower Bounds for Palindromic Length.
3. On Palindromic Length of Sturmian Sequences.
4. On the Length of Shortest Strings Accepted by Two-Way Finite Automata.
5. Separating Many Words by Counting Occurrences of Factors.
6. The Relative Edit-Distance Between Two Input-Driven Languages.
7. k-Spectra of Weakly-c-Balanced Words.

ECML/PKDD (1) 2019

1. String Sanitization: A Combinatorial Approach.

ESA 2019

1. Bidirectional Text Compression in External Memory.
2. Longest Common Substring Made Fully Dynamic.
3. On the Hardness and Inapproximability of Recognizing Wheeler Graphs.
4. Repetition Detection in a Dynamic String.

FCT 2019

1. Circular Pattern Matching with k Mismatches.

FOCS 2019

1. Approximation Algorithms for LCS and LIS with Truly Improved Running Times.
2. Balancing Straight-Line Programs.
3. Optimal Document Exchange and New Codes for Insertions and Deletions.
4. Sublinear Algorithms for Gap Edit Distance.
5. Why are Proof Complexity Lower Bounds Hard?

ICALP 2019

1. Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps.
2. Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication.

INNSBDDL (Tutorials) 2019

1. Learned Data Structures.

ISAAC 2019

1. An Improved Data Structure for Left-Right Maximal Generic Words Problem.
2. Internal Dictionary Matching.
3. On Approximate Range Mode and Range Selection.
4. Top Tree Compression of Tries.

ITCS 2019

1. Testing Local Properties of Arrays.

IWOCA 2019

1. Burrows-Wheeler Transform of Words Defined by Morphisms.
2. Finding Periods in Cartesian Tree Matching.
3. Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings.

LATA 2019

1. Automata over Infinite Sequences of Reals.
2. Efficient Representation and Counting of Antipower Factors in Words.
3. Generalized Register Context-Free Grammars.
4. On the Maximum Number of Distinct Palindromic Sub-arrays.
5. Palindromic Subsequences in Finite Words.
6. Recurrence in Multidimensional Words.
7. Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables.

MFCS 2019

1. A Constant-Time Colored Choice Dictionary with Almost Robust Iteration.
2. From Regular Expression Matching to Parsing.
3. Indexing Graph Search Trees and Applications.
4. RLE Edit Distance in Near Optimal Time.
5. The Power Word Problem.
6. Uniform Random Expressions Lack Expressivity.
7. Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations.

RECOMB 2019

1. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment.

SEA² 2019

1. Searching for Best Karatsuba Recurrences.

SODA 2019

1. Efficiently Approximating Edit Distance Between Pseudorandom Strings.
2. Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts.
3. List Decoding with Double Samplers.
4. Lower Bounds for Oblivious Data Structures.
5. Lower bounds for text indexing with mismatches and differences.
6. Optimal Construction of Compressed Indexes for Highly Repetitive Texts.
7. Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets.
8. The streaming k-mismatch problem.

SOFSEM 2019

1. On Infinite Prefix Normal Words.

SPIRE 2019

1. A New Linear-Time Algorithm for Centroid Decomposition.
2. A Practical Alphabet-Partitioning Rank/Select Data Structure.
3. Adaptive Succinctness.
4. An Index for Sequencing Reads Based on the Colored de Bruijn Graph.
5. An Optimal Algorithm to Find Champions of Tournament Graphs.
6. Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings.
7. BM25 Beyond Query-Document Similarity.
8. Bounds and Estimates on the Average Edit Distance.
9. COBS: A Compact Bit-Sliced Signature Index.
10. Compact Data Structures for Shortest Unique Substring Queries.
11. Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets.
12. Fast Cartesian Tree Matching.
13. Fast Identification of Heavy Hitters by Cached and Packed Group Testing.
14. Fast, Small, and Simple Document Listing on Repetitive Text Collections.
15. Faster Dynamic Compressed d-ary Relations.
16. Faster Repetition-Aware Compressed Suffix Trees Based on Block Trees.
17. Implementing the Topological Model Succinctly.
18. Inducing the Lyndon Array.
19. Linear Time Maximum Segmentation Problems in Column Stream Model.
20. Lossless Image Compression Using List Update Algorithms.
21. Minimal Absent Words in Rooted and Unrooted Trees.
22. Network-Based Pooling for Topic Modeling on Microblog Content.
23. On Longest Common Property Preserved Substring Queries.
24. On the Computation of Longest Previous Non-overlapping Factors.
25. Online Algorithms on Antipowers and Antiperiods.
26. Parallel External Memory Wavelet Tree and Wavelet Matrix Construction.
27. Polynomial-Delay Enumeration of Maximal Common Subsequences.
28. Position Bias Estimation for Unbiased Learning-to-Rank in eCommerce Search.
29. Range Shortest Unique Substring Queries.
30. Rpair: Rescaling RePair with Rsync.
31. Run-Length Encoding in a Finite Universe.
32. SACABench: Benchmarking Suffix Array Construction.
33. Searching Runs in Streams.
34. Space- and Time-Efficient Storage of LiDAR Point Clouds.
35. Space-Efficient Merging of Succinct de Bruijn Graphs.
36. Weighted Shortest Common Supersequence Problem Revisited.

STACS 2019

1. Constant-Time Retrieval with O(log m) Extra Bits.
2. Depth First Search in the Semi-streaming Model.
3. Fast and Longest Rollercoasters.

STOC 2019

1. Local decodability of the Burrows-Wheeler transform.
2. Optimal succinct rank data structure via approximate nonnegative tensor decomposition.
3. String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.

WABI 2019

1. Finding All Maximal Perfect Haplotype Blocks in Linear Time.

WADS 2019

1. Dynamic Dictionary Matching in the Online Model.
2. Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles.

WALCOM 2019

1. Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index.

WORDS 2019

1. Generalized Lyndon Factorizations of Infinite Words.
2. Matching Patterns with Variables.
3. Repetitions in Infinite Palindrome-Rich Words.

ACM J. Exp. Algorithmics 2019

1. Better External Memory LCP Array Construction.

ACM Trans. Algorithms 2019

1. Sparse Dynamic Programming on DAGs with Small Width.

ACM Trans. Inf. Syst. 2019

1. Brotli: A General-Purpose Data Compressor.

Algorithmica 2019

1. Can We Recover the Cover?
2. Correction to: Longest Common Substring with Approximately k Mismatches.
3. Fixed Block Compression Boosting in FM-Indexes: Theory and Practice.
4. Longest Common Substring with Approximately k Mismatches.
5. Mind the Gap! - Online Dictionary Matching with One Gap.
6. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.

Algorithms 2019

1. Compaction of Church Numerals.
2. Space-Efficient Fully Dynamic DFS in Undirected Graphs.

Algorithms Mol. Biol. 2019

1. External memory BWT and LCP computation for sequence collections with applications.
2. Linear time minimum segmentation enables scalable founder reconstruction.
3. Prefix-free parsing for building big BWTs.
4. SNPs detection by eBWT positional clustering.

Bioinform. 2019

1. A framework for space-efficient variable-order Markov models.
2. Compressed filesystem for managing large genome collections.
3. Fully-sensitive seed finding in sequence graphs using a hybrid index.

Comput. J. 2019

1. Context Sensitive Rewriting Codes for Flash Memory†.
2. Edit Distance with Multiple Block Operations†.

Dagstuhl Reports 2019

1. 25 Years of the Burrows-Wheeler Transform (Dagstuhl Seminar 19241).

IEEE Trans. Inf. Theory 2019

1. RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy.

Inf. Comput. 2019

1. Lempel-Ziv compressed structures for document retrieval.
2. On-line weighted pattern matching.

Inf. Process. Lett. 2019

1. Applying the Positional Burrows-Wheeler Transform to all-pairs Hamming distance.
2. Comparison of LZ77-type parsings.

Inf. Sci. 2019

1. GraCT: A Grammar-based Compressed Index for Trajectory Data.

Inf. Syst. 2019

1. On the reproducibility of experiments of indexing repetitive document collections.

J. Comb. Optim. 2019

1. Efficient enumeration of non-equivalent squares in partial words with few holes.

J. Comput. Syst. Sci. 2019

1. Hide and seek with repetitions.

Rev. Socionetwork Strateg. 2019

1. Storing Partitions of Integers in Sublinear Space.

SIAM J. Comput. 2019

1. Bicriteria Data Compression.
2. Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.

SIAM J. Discret. Math. 2019

1. Rollercoasters: Long Sequences without Short Runs.

Softw. Pract. Exp. 2019

1. A compact index for order-preserving pattern matching.

Theor. Comput. Sci. 2019

1. A substring-substring LCS data structure.
2. Algorithms to compute the Burrows-Wheeler Similarity Distribution.
3. Approximate cover of strings.
4. Document listing on repetitive collections with guaranteed performance.
5. Efficient dynamic dictionary matching with DAWGs and AC-automata.
6. Improved upper bounds on all maximal α-gapped repeats and palindromes.
7. Maximal common subsequence algorithms.
8. On overabundant words and their application to biological sequence analysis.
9. On the size of the smallest alphabet for Lyndon trees.
10. Path queries on functions.
11. Succinct data structure for dynamic trees with faster queries.
12. Universal compressed text indexing.

Theory Comput. Syst. 2019

1. Pattern Matching and Consensus Problems on Weighted Sequences and Profiles.

This site is open source. Improve this page.