StringologyTimes

STACS for Stringologist

STACS 2023

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

STACS 2022

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

STACS 2021

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

STACS 2020

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

STACS 2019

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

STACS 2018

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

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. Periods and Borders of Random Words.
  3. Efficiently Finding All Maximal alpha-gapped Repeats.

STACS 2015

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

STACS 2014

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

STACS 2013

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

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.