14 citations · 74 across the 41 of their papers we have counts for
7 papers · 1 filter
Compressed Subsequence Checking is PSPACE-complete
Markus Lohrey
It is shown that the (scattered) subsequence problem for two words represented by straight-line programs is -complete, even over a binary alphabet. The lower bound…
Low-Latency Sliding Window Algorithms for Formal Languages
Moses Ganardi, Louis Jachiet, Markus Lohrey +1
Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For…
Randomized sliding window algorithms for regular languages
Moses Ganardi, Danny Hucke, Markus Lohrey
A sliding window algorithm receives a stream of symbols and has to output at each time instant a certain value which only depends on the last symbols. If the algorithm is rando…
Automata theory on sliding windows
Moses Ganardi, Danny Hucke, Daniel König +2
In a recent paper we analyzed the space complexity of streaming algorithms whose goal is to decide membership of a sliding window to a fixed language. For the class of regular lang…
Efficient Quantile Computation in Markov Chains via Counting Problems for Parikh Images
Christoph Haase, Stefan Kiefer, Markus Lohrey
A cost Markov chain is a Markov chain whose transitions are labelled with non-negative integer costs. A fundamental problem on this model, with applications in the verification of…
Tree compression using string grammars
Moses Ganardi, Danny Hucke, Markus Lohrey +1
We study the compressed representation of a ranked tree by a (string) straight-line program (SLP) for its preorder traversal, and compare it with the well-studied representation by…