4 citations · 4 across the 3 of their papers we have counts for
4 papers · 1 filter
Regular Languages in the Sliding Window Model
Moses Ganardi, Danny Hucke, Markus Lohrey +2
We study the space complexity of the following problem: For a fixed regular language , we receive a stream of symbols and want to test membership of a sliding window of size …
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…
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…