StringologyTimes

STACS for Stringologist

STACS 2023

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

STACS 2022

  1. Probabilistic vs Deterministic Gamblers.
  2. Existential Definability over the Subword Ordering.

STACS 2021

  1. The Edit Distance to k-Subsequence Universality.
  2. Efficiently Testing Simon’s Congruence.
  3. Finding an Optimal Alphabet Ordering for Lyndon Factorization Is Hard.

STACS 2020

  1. A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem.
  2. Using Statistical Encoding to Achieve Tree Succinctness Never Seen Before.
  3. String Indexing with Compressed Patterns.
  4. Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements.
  5. Generalised Pattern Matching Revisited.

STACS 2019

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

STACS 2018

  1. Improving the Upper Bound on the Length of the Shortest Reset Word.
  2. Upper and Lower Bounds for Dynamic Data Structures on Strings.
  3. Relations Between Greedy and Bit-Optimal LZ77 Encodings.
  4. Sums of Palindromes: an Approach via Automata.
  5. Succinct Oblivious RAM.
  6. String Periods in the Order-Preserving Model.
  7. Computing the Longest Common Prefix of a Context-free Language in Polynomial Time.
  8. An Improved Bound for Random Binary Search Trees with Concurrent Insertions.
  9. Space-Efficient Algorithms for Longest Increasing Subsequence.

STACS 2017

  1. On Long Words Avoiding Zimin Patterns.
  2. On the Size of Lempel-Ziv and Lyndon Factorizations.

STACS 2016

  1. External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates.
  2. Efficiently Finding All Maximal alpha-gapped Repeats.
  3. Periods and Borders of Random Words.

STACS 2015

  1. Pattern Matching with Variables: Fast Algorithms and New Hardness Results.
  2. Lempel-Ziv Factorization May Be Harder Than Computing All Runs.
  3. Space-efficient Basic Graph Algorithms.

STACS 2014

  1. Space-Efficient String Indexing for Wildcard Pattern Matching.
  2. Data-Oblivious Data Structures.
  3. Weighted Coloring in Trees.
  4. Faster Compact On-Line Lempel-Ziv Factorization.
  5. Faster Sparse Suffix Sorting.
  6. Testing Generalised Freeness of Words.

STACS 2013

  1. Parameterized Matching in the Streaming Model.
  2. Finding Pseudo-repetitions.
  3. Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries.
  4. Recompression: a simple and powerful technique for word equations.

STACS 2012

  1. Linear-Space Data Structures for Range Mode Query in Arrays.
  2. Tying up the loose ends in fully LZW-compressed pattern matching.

STACS 2011

  1. On Minimal Sturmian Partial Words.

STACS 2010

  1. On Equations over Sets of Integers.

STACS 2009

  1. Compressed Representations of Permutations, and Applications.

STACS 2003

  1. Algorithms for Transposition Invariant String Matching.
This site is open source. Improve this page.