Markus Lohrey

Moses Ganardi, Markus Lohrey

It is shown that the problem of computing the Strahler number of a binary tree given as a term is complete for the circuit complexity class uniform $\mathsf{NC}^1$. For several variants, where the binary tree is given by a pointer structure or in a succinct form by a directed acyclic graph or a tree straight-line program, the complexity of computing the Strahler number is determined as well. We show that the problem of deciding whether a given context-free grammar in Chomsky normal form produces a derivation tree with a Strahler number of at least $k$ is $\mathsf{P}$-complete. If the derivation tree is restricted to be acyclic, the problem becomes $\mathsf{PSPACE}$-complete.

Markus Lohrey

It is shown that the ranked query enumeration problem for a fixed MSO-query on strings can be solved with linear preprocessing and constant delay in the grammar-compressed setting, where the input string is given by a so-called straight-line program, i.e., a context-free grammar that produces exactly one string. Moreover, `ranked' means that the output tuples of the MSO-query are printed in a specific order that has to be MSO-definable. This is the first result for ranked query enumeration on compressed data. A corollary of this result is that for a fixed polyregular function $f$ and a word $w$ that is given by a straight-line program of size $n$, one can list after preprocessing time $\mathcal{O}(n)$ the symbols in $f(w)$ from left to right with constant delay, which generalizes a result of Bojanczyk for the case where $w$ is uncompressed. The proofs for these results are based on factorization trees, which are made accessible to the grammar-compressed setting (a contribution of independent interest).

Markus Lohrey, Lukas Lück, Alexander Thumm et al.

We investigate deterministic and randomized streaming algorithms for word problems in finitely generated groups and semigroups. For this we introduce the notion of a distinguisher: a randomized streaming algorithm that processes two input words in parallel and, with high probability, reaches identical memory states if the words represent the same element, and distinct states otherwise. We construct such distinguishers with low error probability using logarithmic, and in some cases doubly logarithmic, space. For example, our results apply to linear semigroups and to semigroups obtained (under suitable restrictions) via standard constructions such as graph products, wreath products, and semilattice decompositions. In case of commutative semigroups and cancellative nilpotent semigroups, we achieve space complexity $\mathcal{O}(\log \log n)$. We complement these upper bounds with lower bounds demonstrating that certain well-known semigroups do not admit sublinear-space distinguishers. This includes, for example, free inverse monoids of rank at least two and Thompson's group $F$. Finally, we study randomized streaming algorithms for subgroup membership problems in free groups and their direct products.

Markus Lohrey, Markus L. Schmid

We study the problem of enumerating the answers to a query formulated in monadic second order logic (MSO) over an unranked forest F that is compressed by a straight-line program (SLP) D. Our main result states that this can be done after O(|D|) preprocessing and with output-linear delay (in data complexity). This is a substantial improvement over the previously known algorithms for MSO-evaluation over trees, since the compressed size |D| might be much smaller than (or even logarithmic in) the actual data size |F|, and there are linear time SLP-compressors that yield very good compressions on practical inputs. In particular, this also constitutes a meta-theorem in the field of algorithmics on SLP-compressed inputs: all enumeration problems on trees or strings that can be formulated in MSO-logic can be solved with linear preprocessing and output-linear delay, even if the inputs are compressed by SLPs. We also show that our approach can support vertex relabelling updates in time that is logarithmic in the uncompressed data. Our result extends previous work on the enumeration of MSO-queries over uncompressed trees and on the enumeration of document spanners over compressed text documents.

Moses Ganardi, Danny Hucke, Markus Lohrey et al.

We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window $n$ and a stream of symbols. At each time instant, we must decide whether the suffix of length $n$ of the current stream ("the active window") belongs to a given regular language. Recent works showed that the space complexity of an optimal deterministic sliding window algorithm for this problem is either constant, logarithmic or linear in the window size $n$ and provided natural language theoretic characterizations of the space complexity classes. Subsequently, those results were extended to randomized algorithms to show that any such algorithm admits either constant, double logarithmic, logarithmic or linear space complexity. In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We consider deterministic and randomized sliding window property testers with one-sided and two-sided errors. In particular, we show that for any regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.