Search

Das Ziel grammatik-basierter Datenkompression ist es ein Wort (oder einen Text) durch eine kontextfreie Grammatik darzustellen, die ausschließlich dieses Wort erzeugt. Eine kontextfreie Grammatik mit dieser Eigenschaft wird als Straight-line Program (SLP) bezeichnet. Grammatik-basierte Kompression ist ein nützliches Werkzeug um Daten zu komprimieren und verschiedene Anfragen effizient mit Hilfe der komprimierten Repräsentation zu beantworten ohne diese vorher zu dekomprimieren. Im ersten Teil dieser Arbeit werden die grammatikbasierten Kompressoren LZ78, BiSection, RePair, Greedy und LongestMatch untersucht, die zu den bekanntesten Algorithmen in diesem Bereich zählen. In der bedeutenden Veröffentlichung "The smallest grammar problem" von Charikar et al. wurden untere und obere Schranken für die Approximationsgüte verschiedenster grammatik-basierter Kompressoren gezeigt, darunter die oben genannten. Leider besteht für jeden Algorithmus eine Lücke zwischen der unteren und oberen Schranke. In dieser Arbeit werden diese Lücken für die Kompressoren LZ78 und BiSection geschlossen. Des Weiteren werd für RePair und für Greedy die unteren Schranken verbessert. Ein weiteres Ergebnis dieser Arbeit verbessert ein Resultat von Arpe und Reischuk, welches grammatik-basierte Kompression über beliebigen Alphabeten und binären Alphabeten verbindet. Im zweiten Teil dieser Arbeit betrachten wir grammatik-basierte Kompression für Bäume. Das Prinzip ist ähnlich, da in diesem Kontext ein Baum durch eine lineare, kontextfreie Baumgrammatik erzeugt wird. Eine solche Grammatik wird Tree Straight-line Program (TSLP) genannt. Als Hauptresultat in diesem Zusammenhang werden zwei Algorithmen präsentiert, die für einen Baum mit n Knoten und konstant vielen verschiedenen Beschriftungen der Knoten ein TSLP der Gr öße O(n/log n) generieren. Zusätzlich wird erreicht, dass das TSLP logarithmische Tiefe hat. Diese Eigenschaften können in logarithmischen Platz oder alternativ in linearer Zeit erreicht werden. Entsprechende Resultate für grammatik-basierte Kompression von Wörtern sind wohl bekannt. Es werden zusätzlich zwei Anwendungen präsentiert: Zuerst werden TSLPs für die Umwandlung von arithmetischen Formeln zu arithmetischen Schaltkreisen der Größe O((n*log m)/log n) und Tiefe O(log n) genutzt, wobei n die Größe der Formel und m die Anzahl verschiedener Variablen in der Formel ist. Als zweite Anwendung wird eine binäre Kodierung von unbeschrifteten Binärbäumen auf der Basis von grammatik-basierter Baumkompression präsentiert. Es wird gezeigt, dass diese Kodierung unter gewissen Voraussetzungen asymptotisch optimal ist., The goal of grammar-based compression is to represent a string by a small context-free grammar that produces only this string. Such a grammar is called a straight-line program (SLP). Grammar-based compression is a powerful tool to efficiently store data and process the compressed representation without decompressing it. In the first part of this work, we study the grammar-based compressors LZ78, BiSection, Repair, Greedy and LongestMatch, which are among the most popular compressors in this area. In the seminal work "The smallest grammar problem" by Charikar et al., the authors derived lower and upper bounds on the approximation ratios of several grammar-based compressors including the algorithms mentioned above. Unfortunately, for none of the compressors the presented bounds matched. Here, we close the gaps for LZ78 and BiSection. For RePair and Greedy we improve the lower bounds. Moreover, we improve a result of Arpe and Reischuk which relates grammar-based compression for arbitrary alphabets and binary alphabets. In the second part of this work, we consider grammar-based compression for trees. The main principle is similar, because the goal is to represent a tree by a small linear context-free tree grammar that produces only this tree. Such a tree grammar is called a tree straight-line program (TSLP). As a main contribution, we present two algorithms that produce a TSLP of size O(n/log n) for any given tree with n nodes and a constant set of node labels, where we assume that the maximal number of children of a node in the tree is also bounded by a constant. Additionally, the obtained TSLP has logarithmic depth. We show that those properties can be achieved in logarithmic space, or alternatively, in linear time. Similar results on the worst-case size of SLPs are well known. We use our constructions for two applications: First, we apply TSLPs to the problem of transforming arithmetical formulas into equivalent circuits of size O((n*log m)/log n) and depth O(log n), where n is the size of the formula and m is number of different variables occurring in the formula. As a second application, we present a binary encoding of unlabeled binary trees based on grammar-based tree compression. We prove that this encoding is worst-case universal and thus asymptotically optimal for certain tree sources.

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., Comment: A short version of this paper was accepted for presentation at ISAAC 2019

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 languages we proved a space trichotomy theorem: for every regular language the optimal space bound is either constant, logarithmic or linear. In this paper we continue this line of research: We present natural characterizations for the constant and logarithmic space classes and establish tight relationships to the concept of language growth. We also analyze the space complexity with respect to automata size and prove almost matching lower and upper bounds. Finally, we consider the decision problem whether a language given by a DFA/NFA admits a sliding window algorithm using logarithmic/constant space., Extended version of a paper presented at STACS 2018

The computational complexity of the circuit evaluation problem for finite semirings is considered, where semirings are not assumed to have an additive or multiplicative identity. The following dichotomy is shown: If a finite semiring is such that (i) the multiplicative semigroup is solvable and (ii) it does not contain a subsemiring with an additive identity $0$ and a multiplicative identity $1 \neq 0$, then the circuit evaluation problem for the semiring is in $\mathsf{DET} \subseteq \mathsf{NC}^2$. In all other cases, the circuit evaluation problem is $\mathsf{P}$-complete., Some proof details from the previous version are simplified in the new version

We study the space complexity of querying regular languages over data streams in the sliding window model. The algorithm has to answer at any point of time whether the content of the sliding window belongs to a fixed regular language. A trichotomy is shown: For every regular language the optimal space requirement is either in Theta(n), Theta(log(n)), or constant, where $n$ is the size of the sliding window.

It is shown that every tree of size n over a fixed set of sigma different ranked symbols can be decomposed into O(n/log_sigma(n)) = O((n * log(sigma))/ log(n)) many hierarchically defined pieces. Formally, such a hierarchical decomposition has the form of a straight-line linear context-free tree grammar of size O(n/log_sigma(n)), which can be used as a compressed representation of the input tree. This generalizes an analogous result for strings. Previous grammar-based tree compressors were not analyzed for the worst-case size of the computed grammar, except for the top dag of Bille et al., for which only the weaker upper bound of O(n/log^{0.19}(n)) for unranked and unlabelled trees has been derived. The main result is used to show that every arithmetical formula of size n, in which only m

We apply so-called tree straight-line programs to the problem of universal source coding for binary trees. We derive an upper bound on the maximal pointwise redundancy (or worst-case redundancy) that improve previous bounds on the average case redundancy obtained by Zhang, Yang, and Kieffer using directed acyclic graphs. Using this, we obtain universal codes for new classes of tree sources.