StringologyTimes

STACS for Stringologist

STACS 2023

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

STACS 2022

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

STACS 2021

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

STACS 2020

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

STACS 2018

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

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. Space-efficient Basic Graph Algorithms.
  2. Pattern Matching with Variables: Fast Algorithms and New Hardness Results.
  3. Lempel-Ziv Factorization May Be Harder Than Computing All Runs.

STACS 2014

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

STACS 2013

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

STACS 2012

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

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.