Search

We present a linear preprocessing and output-linear delay enumeration algorithm for MSO-queries over trees that are compressed in the well-established grammar-based framework. Time bounds are measured with respect to the size of the compressed representation of the tree. 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.

We study the space complexity of the following problem: For a fixed regular language $L$, test membership of a sliding window of length $n$ to $L$ over a given stream of symbols. For deterministic streaming algorithms we prove a trichotomy theorem, namely that the (optimal) space complexity is either constant, logarithmic or linear, measured in the window length $n$. Additionally, we provide natural language-theoretic characterizations of the space classes. We then extend the results to randomized streaming algorithms and we show that in this setting, the space complexity of any regular language is either constant, doubly logarithmic, logarithmic or linear. Finally, we introduce sliding window testers, which can distinguish whether a window belongs to the language $L$ or has Hamming distance $> \epsilon n$ to $L$. We prove that every regular language has a deterministic (resp., randomized) sliding window tester that requires only logarithmic (resp., constant) space., Comment: arXiv admin note: text overlap with arXiv:1909.10261

We study the parameterized complexity of the following factorization problem: given elements $a,a_1, \ldots, a_m$ of a monoid and a parameter $k$, can $a$ be written as the product of at most (or exactly) $k$ elements from $a_1, \ldots, a_m$. Several new upper bounds and fpt-equivalences with more restricted problems (subset sum and knapsack) are shown. Finally, some new upper bounds for variants of the parameterized change-making problems are shown.

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 every regular language $L$ it is shown that there exists a constant-latency solution that supports adding and removing symbols independently on both ends of the window (the so-called two-way variable-size model). We prove that this result extends to all visibly pushdown languages. For deterministic 1-counter languages we present a $\mathcal{O}(\log n)$ latency sliding window algorithm for the two-way variable-size model where $n$ refers to the window size. We complement these results with a conditional lower bound: there exists a fixed real-time deterministic context-free language $L$ such that, assuming the OMV (online matrix vector multiplication) conjecture, there is no sliding window algorithm for $L$ with latency $n^{1/2-\epsilon}$ for any $\epsilon>0$, even in the most restricted sliding window model (one-way fixed-size model). The above mentioned results all refer to the unit-cost RAM model with logarithmic word size. For regular languages we also present a refined picture using word sizes $\mathcal{O}(1)$, $\mathcal{O}(\log\log n)$, and $\mathcal{O}(\log n)$., Comment: A short version will be presented at the conference FSTTCS 2022

We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed $n \geq 3$, where $n$ is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks, which states NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar., Comment: A short version will appear in the proceedings of MFCS 2022

We study deterministic and randomized streaming algorithms for word problems of finitely generated groups. For finitely generated linear groups, metabelian groups and free solvable groups we show the existence of randomized streaming algorithms with logarithmic space complexity for their word problems. We also show that the class of finitely generated groups with a logspace randomized streaming algorithm for the word problem is closed under several group theoretical constructions: finite extensions, graph products and wreath products by free abelian groups. We contrast these results with several lower bound. An example of a finitely presented group, where the word problem has only a linear space randomized streaming algorithm, is Thompson's group $F$. Finally, randomized streaming algorithms for subgroup membership problems in free groups and direct products of free groups are studied., Comment: arXiv admin note: text overlap with arXiv:2101.06132 by other authors

We consider exponent equations in finitely generated groups. These are equations, where the variables appear as exponents of group elements and take values from the natural numbers. Solvability of such (systems of) equations has been intensively studied for various classes of groups in recent years. In many cases, it turns out that the set of all solutions on an exponent equation is a semilinear set that can be constructed effectively. Such groups are called knapsack semilinear. Examples of knapsack semilinear groups are hyperbolic groups, virtually special groups, co-context-free groups and free solvable groups. Moreover, knapsack semilinearity is preserved by many group theoretic constructions, e.g., finite extensions, graph products, wreath products, amalgamated free products with finite amalgamated subgroups, and HNN-extensions with finite associated subgroups. On the other hand, arbitrary HNN-extensions do not preserve knapsack semilinearity. In this paper, we consider the knapsack semilinearity of HNN-extensions, where the stable letter $t$ acts trivially by conjugation on the associated subgroup $A$ of the base group $G$. We show that under some additional technical conditions, knapsack semilinearity transfers from base group $G$ to the HNN-extension $H$. These additional technical conditions are satisfied in many cases, e.g., when $A$ is a centralizer in $G$ or $A$ is a quasiconvex subgroup of the hyperbolic group $G$., Comment: Published in Journal of Groups, Complexity, Cryptology. A short version appeared in Proceedings of ISSAC 2022

The power word problem for a group $G$ asks whether an expression $u_1^{x_1} \cdots u_n^{x_n}$, where the $u_i$ are words over a finite set of generators of $G$ and the $x_i$ binary encoded integers, is equal to the identity of $G$. It is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over $G$). We start by showing some easy results concerning the power word problem. In particular, the power word problem for a group $G$ is $NC^1$-many-one reducible to the power word problem for a finite-index subgroup of $G$. For our main result, we consider graph products of groups that do not have elements of order two. We show that the power word problem in a fixed such graph product is $AC^0$-Turing-reducible to the word problem for the free group $F_2$ and the power word problems of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups $\mathcal{C}$ without order two elements, the uniform power word problem in a graph product can be solved in $\mathsf{AC^0(C_=L^{UPowWP(\mathcal{C})})}$, where $UPowWP(\mathcal{C})$ denotes the uniform power word problem for groups from the class $\mathcal{C}$. As a consequence of our results, the uniform knapsack problem in right-angled Artin groups is NP-complete. The present paper is a combination of the two conference papers. In [StoberW22] and previous iterations of this paper our results on graph products were wrongly stated without the additional assumption that the base groups do not have elements of order two. In the present work we correct this mistake. While we strongly conjecture that the result as stated previously is true, our proof relies on this additional assumption., Comment: Version 3 fixes a mistake in the previous versions. There our results on graph products were wrongly stated without the additional assumption that the base groups do not have elements of order two. Version 3 also includes some content from arXiv:1904.08343

The computational complexity of the word problem in HNN-extension of groups is studied. HNN-extension is a fundamental construction in combinatorial group theory. It is shown that the word problem for an ascending HNN-extension of a group H is logspace reducible to the so-called compressed word problem for H. The main result of the paper states that the word problem for an HNN-extension of a hyperbolic group H with cyclic associated subgroups can be solved in polynomial time. This result can be easily extended to fundamental groups of graphs of groups with hyperbolic vertex groups and cyclic edge groups., Comment: An extended abstract will be presented at FCT 2021

Whereas for strings, higher-order empirical entropy is the standard entropy measure, several different notions of empirical entropy for trees have been proposed in the past, notably label entropy, degree entropy, conditional versions of the latter two, and empirical entropy of trees (here, called label-shape entropy). In this paper, we carry out a systematic comparison of these entropy measures. We underpin our theoretical investigations by experimental results with real XML data.

We prove new complexity results for computational problems in certain wreath products of groups and (as an application) for free solvable group. For a finitely generated group we study the so-called power word problem (does a given expression $u_1^{k_1} \ldots u_d^{k_d}$, where $u_1, \ldots, u_d$ are words over the group generators and $k_1, \ldots, k_d$ are binary encoded integers, evaluate to the group identity?) and knapsack problem (does a given equation $u_1^{x_1} \ldots u_d^{x_d} = v$, where $u_1, \ldots, u_d,v$ are words over the group generators and $x_1,\ldots,x_d$ are variables, has a solution in the natural numbers). We prove that the power word problem for wreath products of the form $G \wr \mathbb{Z}$ with $G$ nilpotent and iterated wreath products of free abelian groups belongs to $\mathsf{TC}^0$. As an application of the latter, the power word problem for free solvable groups is in $\mathsf{TC}^0$. On the other hand we show that for wreath products $G \wr \mathbb{Z}$, where $G$ is a so called uniformly strongly efficiently non-solvable group (which form a large subclass of non-solvable groups), the power word problem is $\mathsf{coNP}$-hard. For the knapsack problem we show $\mathsf{NP}$-completeness for iterated wreath products of free abelian groups and hence free solvable groups. Moreover, the knapsack problem for every wreath product $G \wr \mathbb{Z}$, where $G$ is uniformly efficiently non-solvable, is $\Sigma^2_p$-hard.

We prove that the power word problem for certain metabelian subgroups of $\mathsf{GL}(2,\mathbb{C})$ (including the solvable Baumslag-Solitar groups $\mathsf{BS}(1,q) = \langle a,t \mid t a t^{-1} = a^q \rangle$) belongs to the circuit complexity class $\mathsf{TC}^0$. In the power word problem, the input consists of group elements $g_1, \ldots, g_d$ and binary encoded integers $n_1, \ldots, n_d$ and it is asked whether $g_1^{n_1} \cdots g_d^{n_d} = 1$ holds. Moreover, we prove that the knapsack problem for $\mathsf{BS}(1,q)$ is $\mathsf{NP}$-complete. In the knapsack problem, the input consists of group elements $g_1, \ldots, g_d,h$ and it is asked whether the equation $g_1^{x_1} \cdots g_d^{x_d} = h$ has a solution in $\mathbb{N}^d$. For the more general case of a system of so-called exponent equations, where the exponent variables $x_i$ can occur multiple times, we show that solvability is undecidable for $\mathsf{BS}(1,q)$., Comment: A short version appeared in the proceedings of MFCS 2020

We show that the following group constructions preserve the semilinearity of the solution sets for knapsack equations (equations of the form $g_1^{x_1} \cdots g_k^{x_k} = g$ in a group $G$, where the variables $x_1, \ldots, x_k$ take values in the natural numbers): graph products, amalgamated free products with finite amalgamated subgroups, HNN-extensions with finite associated subgroups, and finite extensions. Moreover, we study the dependence of the so-called magnitude for the solution set of a knapsack equation (the magnitude is a complexity measure for semi-linear sets) with respect to the length of the knapsack equation (measured in number of generators). We investigate, how this dependence changes under the above group operations.

We give lower bounds on the complexity of the word problem of certain non-solvable groups: for a large class of non-solvable infinite groups, including in particular free groups, Grigorchuk's group and Thompson's groups, we prove that their word problem is $\mathsf{NC}^1$-hard. For some of these groups (including Grigorchuk's group and Thompson's groups) we prove that the compressed word problem (which is equivalent to the circuit evaluation problem) is $\mathsf{PSPACE}$-complete., Comment: A short version of the paper will appear in the Proceedings of the Computational Complexity Conference 2020

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 seminal paper of Charikar et al. on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Here the gaps for $\mathsf{LZ78}$ and $\mathsf{BISECTION}$ are closed by showing that the approximation ratio of $\mathsf{LZ78}$ is $\Theta( (n/\log n)^{2/3})$, whereas the approximation ratio of $\mathsf{BISECTION}$ is $\Theta(\sqrt{n/\log n})$. In addition, the lower bound for $\mathsf{RePair}$ is improved from $\Omega(\sqrt{\log n})$ to $\Omega(\log n/\log\log n)$. Finally, results of Arpe and Reischuk relating grammar-based compression for arbitrary alphabets and binary alphabets are improved., Comment: A short version of this paper appeared in the Proceedings of SPIRE 2016. This work has been supported by the DFG research project LO 748/10-1 (QUANT-KOMP)

In this work we introduce a new succinct variant of the word problem in a finitely generated group $G$, which we call the power word problem: the input word may contain powers $p^x$, where $p$ is a finite word over generators of $G$ and $x$ is a binary encoded integer. The power word problem is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over $G$). The main result of the paper states that the power word problem for a finitely generated free group $F$ is AC$^0$-Turing-reducible to the word problem for $F$. Moreover, the following hardness result is shown: For a wreath product $G \wr \mathbb{Z}$, where $G$ is either free of rank at least two or finite non-solvable, the power word problem is complete for coNP. This contrasts with the situation where $G$ is abelian: then the power word problem is shown to be in TC$^0$.

It is shown that a context-free grammar of size $m$ that produces a single string $w$ (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for $w$ of size $\mathcal{O}(m)$, whose unique derivation tree has depth $\mathcal{O}(\log |w|)$. This solves an open problem in the area of grammar-based compression. Similar results are shown for two formalism for grammar-based tree compression: top dags and forest straight-line programs. These balancing results are all deduced from a single meta theorem stating that the depth of an algebraic circuit over an algebra with a certain finite base property can be reduced to $\mathcal{O}(\log n)$ with the cost of a constant multiplicative size increase. Here, $n$ refers to the size of the unfolding (or unravelling) of the circuit., Comment: An extended abstract of this paper appears in the Proceedings of FOCS 2019

The definition of $k^{th}$-order empirical entropy of strings is extended to node labelled binary trees. A suitable binary encoding of tree straight-line programs (that have been used for grammar-based tree compression before) is shown to yield binary tree encodings of size bounded by the $k^{th}$-order empirical entropy plus some lower order terms. This generalizes recent results for grammar-based string compression to grammar-based tree compression., Comment: A short version of this paper appeared in the IEEE Proceedings of ISIT 2019

We prove that the compressed word problem and the compressed simultaneous conjugacy problem are solvable in polynomial time in hyperbolic groups. In such problems, group elements are input as words defined by straight line programs defined over a finite generating set for the group. We prove also that, for any infinite hyperbolic group $G$, the compressed knapsack problem in $G$ is ${\mathsf{NP}}$-complete., Comment: Improved version of the previous paper

Recently knapsack problems have been generalized from the integers to arbitrary finitely generated groups. The knapsack problem for a finitely generated group $G$ is the following decision problem: given a tuple $(g, g_1, \ldots, g_k)$ of elements of $G$, are there natural numbers $n_1, \ldots, n_k \in \mathbb{N}$ such that $g = g_1^{n_1} \cdots g_k^{n_k}$ holds in $G$? Myasnikov, Nikolaev, and Ushakov proved that for every (Gromov-)hyperbolic group, the knapsack problem can be solved in polynomial time. In this paper, the precise complexity of the knapsack problem for hyperbolic group is determined: for every hyperbolic group $G$, the knapsack problem belongs to the complexity class $\mathsf{LogCFL}$, and it is $\mathsf{LogCFL}$-complete if $G$ contains a free group of rank two. Moreover, it is shown that for every hyperbolic group $G$ and every tuple $(g, g_1, \ldots, g_k)$ of elements of $G$ the set of all $(n_1, \ldots, n_k) \in \mathbb{N}^k$ such that $g = g_1^{n_1} \cdots g_k^{n_k}$ in $G$ is semilinear and a semilinear representation where all integers are of size polynomial in the total geodesic length of the $g, g_1, \ldots, g_k$ can be computed. Groups with this property are also called knapsack-tame. This enables us to show that knapsack can be solved in $\mathsf{LogCFL}$ for every group that belongs to the closure of hyperbolic groups under free products and direct products with $\mathbb{Z}$.

In this paper the computational complexity of the (bi)simulation problem over restricted graph classes is studied. For trees given as pointer structures or terms the (bi)simulation problem is complete for logarithmic space or NC$^1$, respectively. This solves an open problem from Balc\'azar, Gabarr\'o, and S\'antha. Furthermore, if only one of the input graphs is required to be a tree, the bisimulation (simulation) problem is contained in AC$^1$ (LogCFL). In contrast, it is also shown that the simulation problem is P-complete already for graphs of bounded path-width.

We study the average number of distinct fringe subtrees in random trees generated by leaf-centric binary tree sources as introduced by Zhang, Yang and Kieffer. A leaf-centric binary tree source induces for every $n \geq 2$ a probability distribution on the set of binary trees with $n$ leaves. We generalize a result by Flajolet, Gourdon, Martinez and Devroye, according to which the average number of distinct fringe subtrees in a random binary search tree of size $n$ is in $\Theta(n/\log n)$, as well as a result by Flajolet, Sipala and Steayert, according to which the number of distinct fringe subtrees in a uniformly random binary tree of size $n$ is in $\Theta(n/\sqrt{\log n})$.

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 $n$ symbols. If the algorithm is randomized, then at each time instant it produces an incorrect output with probability at most $\epsilon$, which is a constant error bound. This work proposes a more relaxed definition of correctness which is parameterized by the error bound $\epsilon$ and the failure ratio $\phi$: A randomized sliding window algorithm is required to err with probability at most $\epsilon$ at a portion of $1-\phi$ of all time instants of an input stream. This work continues the investigation of sliding window algorithms for regular languages. In previous works a trichotomy theorem was shown for deterministic algorithms: the optimal space complexity is either constant, logarithmic or linear in the window size. The main results of this paper concerns three natural settings (randomized algorithms with failure ratio zero and randomized/deterministic algorithms with bounded failure ratio) and provide natural language theoretic characterizations of the space complexity classes.

We introduce forest straight-line programs (FSLPs) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of FSLPs with two other compression schemes for unranked trees: top dags and tree straight-line programs of first-child/next sibling encodings. Efficient translations between these formalisms are provided. Finally, we show that equality of unranked trees in the setting where certain symbols are associative or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees., Comment: Extended version of a paper at CSR 2018

It is shown that for a given ordered node-labelled tree of size $n$ and with $s$ many different node labels, one can construct in linear time a top dag of height $O(\log n)$ and size $O(n / \log_\sigma n) \cap O(d \cdot \log n)$, where $\sigma = \max\{ 2, s\}$ and $d$ is the size of the minimal dag. The size bound $O(n / \log_\sigma n)$ is optimal and improves on previous bounds.

In recent years, knapsack problems for (in general non-commutative) groups have attracted attention. In this paper, the knapsack problem for wreath products is studied. It turns out that decidability of knapsack is not preserved under wreath product. On the other hand, the class of knapsack-semilinear groups, where solutions sets of knapsack equations are effectively semilinear, is closed under wreath product. As a consequence, we obtain the decidability of knapsack for free solvable groups. Finally, it is shown that for every non-trivial abelian group $G$, knapsack (as well as the related subset sum problem) for the wreath product $G \wr \mathbb{Z}$ is NP-complete.

We present a general framework for balancing expressions (terms) in form of so called tree straight-line programs. The latter can be seen as circuits over the free term algebra extended by contexts (terms with a hole) and the operations which insert terms/contexts into contexts. It is shown that for every term one can compute in DLOGTIME-uniform TC$^0$ a tree straight-line program of logarithmic depth and size $O(n/\log n)$. This allows reducing the term evaluation problem over an arbitrary algebra $\mathcal{A}$ to the term evaluation problem over a derived two-sorted algebra $\mathcal{F}(\mathcal{A})$. Several applications are presented: (i) an alternative proof for a recent result by Krebs, Limaye and Ludwig on the expression evaluation problem is given, (ii) it is shown that expressions for an arbitrary (possibly non-commutative) semiring can be transformed in DLOGTIME-uniform TC$^0$ into equivalent circuits of logarithmic depth and size $O(n/\log n)$, and (iii) a corresponding result for regular expressions is shown.

In a seminal paper of Charikar et al.~on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors. Here we improve the lower bound for the famous {\sf RePair} algorithm from $\Omega(\sqrt{\log n})$ to $\Omega(\log n/\log\log n)$. The family of words used in our proof is defined over a binary alphabet, while the lower bound from Charikar et al. needs an alphabet of logarithmic size in the length of the provided words.

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., Comment: Extended version of a paper presented at STACS 2018

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

Myasnikov et al. have introduced the knapsack problem for arbitrary finitely generated groups. In previous work, the authors proved that for each graph group, the knapsack problem can be solved in $\mathsf{NP}$. Here, we determine the exact complexity of the problem for every graph group. While the problem is $\mathsf{TC}^0$-complete for complete graphs, it is $\mathsf{LogCFL}$-complete for each (non-complete) transitive forest. For every remaining graph, the problem is $\mathsf{NP}$-complete., Comment: 26 pages, 2 figures

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., Comment: Some proof details from the previous version are simplified in the new version

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 stochastic systems, is to compute information about the distribution of the total cost accumulated in a run. This includes the probability of large total costs, the median cost, and other quantiles. While expectations can be computed in polynomial time, previous work has demonstrated that the computation of cost quantiles is harder but can be done in PSPACE. In this paper we show that cost quantiles in cost Markov chains can be computed in the counting hierarchy, thus providing evidence that computing those quantiles is likely not PSPACE-hard. We obtain this result by exhibiting a tight link to a problem in formal language theory: counting the number of words that are both accepted by a given automaton and have a given Parikh image. Motivated by this link, we comprehensively investigate the complexity of the latter problem. Among other techniques, we rely on the so-called BEST theorem for efficiently computing the number of Eulerian circuits in a directed graph.

A grammar-compressed ranked tree is represented with a linear space overhead so that a single traversal step, i.e., the move to the parent or the i-th child, can be carried out in constant time. Moreover, we extend our data structure such that equality of subtrees can be checked in constant time.

It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for graph groups. This result even holds if the group elements are represented in a compressed form by SLPs, which generalizes the classical NP-completeness result of the integer knapsack problem. We also prove general transfer results: NP-membership of the knapsack problem is passed on to finite extensions, HNN-extensions over finite associated subgroups, and amalgamated products with finite identified subgroups., Comment: 42 pages

It is shown that the knapsack problem (introduced by Myasnikov, Nikolaev, and Ushakov) is undecidable in a direct product of sufficiently many copies of the discrete Heisenberg group (which is nilpotent of class 2). Moreover, for the discrete Heisenberg group itself, the knapsack problem is decidable. Hence, decidability of the knapsack problem is not preserved under direct products. It is also shown that for every co-context-free group, the knapsack problem is decidable. For the subset sum problem (also introduced by Myasnikov, Nikolaev, and Ushakov) we show that it belongs to the class NL (nondeterministic logspace) for every finitely generated virtually nilpotent group and that there exists a polycyclic group with an NP-complete subset sum problem.

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 straight-line context free tree grammars (which are also known as tree straight-line programs or TSLPs). Although SLPs turn out to be exponentially more succinct than TSLPs, we show that many simple tree queries can still be performed efficiently on SLPs, such as computing the height and Horton-Strahler number of a tree, tree navigation, or evaluation of Boolean expressions. Other problems on tree traversals turn out to be intractable, e.g. pattern matching and evaluation of tree automata.

Straight-line (linear) context-free tree (SLT) grammars have been used to compactly represent ordered trees. It is well known that equivalence of SLT grammars is decidable in polynomial time. Here we extend this result and show that isomorphism of unordered trees given as SLT grammars is decidable in polynomial time. The proof constructs a compressed version of the canonical form of the tree represented by the input SLT grammar. The result is generalized to unrooted trees by "re-rooting" the compressed trees in polynomial time. We further show that bisimulation equivalence of unrooted unordered trees represented by SLT grammars is decidable in polynomial time. For non-linear SLT grammars which can have double-exponential compression ratios, we prove that unordered isomorphism is PSPACE-hard and in EXPTIME. The same complexity bounds are shown for bisimulation equivalence.

Powerful skew arithmetic circuits are introduced. These are skew arithmetic circuits with variables, where input gates can be labelled with powers $x^n$ for binary encoded numbers $n$. It is shown that polynomial identity testing for powerful skew arithmetic circuits belongs to $\mathsf{coRNC}^2$, which generalizes a corresponding result for (standard) skew circuits. Two applications of this result are presented: (i) Equivalence of higher-dimensional straight-line programs can be tested in $\mathsf{coRNC}^2$; this result is even new in the one-dimensional case, where the straight-line programs produce strings. (ii) The compressed word problem (or circuit evaluation problem) for certain wreath products of finitely generated abelian groups belongs to $\mathsf{coRNC}^2$.

The circuit evaluation problem (also known as the compressed word problem) for finitely generated linear groups is studied. The best upper bound for this problem is $\mathsf{coRP}$, which is shown by a reduction to polynomial identity testing. Conversely, the compressed word problem for the linear group $\mathsf{SL}_3(\mathbb{Z})$ is equivalent to polynomial identity testing. In the paper, it is shown that the compressed word problem for every finitely generated nilpotent group is in $\mathsf{DET} \subseteq \mathsf{NC}^2$. Within the larger class of polycyclic groups we find examples where the compressed word problem is at least as hard as polynomial identity testing for skew arithmetic circuits.

Metric temporal logic (MTL) and timed propositional temporal logic (TPTL) are quantitative extensions of linear temporal logic, which are prominent and widely used in the verification of real-timed systems. It was recently shown that the path checking problem for MTL, when evaluated over finite timed words, is in the parallel complexity class NC. In this paper, we derive precise complexity results for the path-checking problem for MTL and TPTL when evaluated over infinite data words over the non-negative integers. Such words may be seen as the behaviours of one-counter machines. For this setting, we give a complete analysis of the complexity of the path-checking problem depending on the number of register variables and the encoding of constraint numbers (unary or binary). As the two main results, we prove that the path-checking problem for MTL is P-complete, whereas the path-checking problem for TPTL is PSPACE-complete. The results yield the precise complexity of model checking deterministic one-counter machines against formulae of MTL and TPTL.

Recently, we have shown that satisfiability for $\mathsf{ECTL}^*$ with constraints over $\mathbb{Z}$ is decidable using a new technique. This approach reduces the satisfiability problem of $\mathsf{ECTL}^*$ with constraints over some structure A (or class of structures) to the problem whether A has a certain model theoretic property that we called EHD (for "existence of homomorphisms is decidable"). Here we apply this approach to concrete domains that are tree-like and obtain several results. We show that satisfiability of $\mathsf{ECTL}^*$ with constraints is decidable over (i) semi-linear orders (i.e., tree-like structures where branches form arbitrary linear orders), (ii) ordinal trees (semi-linear orders where the branches form ordinals), and (iii) infinitely branching trees of height h for each fixed $h\in \mathbb{N}$. We prove that all these classes of structures have the property EHD. In contrast, we introduce Ehrenfeucht-Fraisse-games for $\mathsf{WMSO}+\mathsf{B}$ (weak $\mathsf{MSO}$ with the bounding quantifier) and use them to show that the infinite (order) tree does not have property EHD. As a consequence, a different approach has to be taken in order to settle the question whether satisfiability of $\mathsf{ECTL}^*$ (or even $\mathsf{LTL}$) with constraints over the infinite (order) tree is decidable.

It is shown that every tree of size $n$ over a fixed set of $\sigma$ different ranked symbols can be decomposed (in linear time as well as in logspace) into $O\big(\frac{n}{\log_\sigma n}\big) = O\big(\frac{n \log \sigma}{\log n}\big)$ many hierarchically defined pieces. Formally, such a hierarchical decomposition has the form of a straight-line linear context-free tree grammar of size $O\big(\frac{n}{\log_\sigma n}\big)$, 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\big(\frac{n}{\log_\sigma^{0.19} n}\big)$ (which was very recently improved to $O\big(\frac{n \cdot \log \log_\sigma n}{\log_\sigma n}\big)$ by H\"ubschle-Schneider and Raman) 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 \leq n$ different variables occur, can be transformed (in linear time as well as in logspace) into an arithmetical circuit of size $O\big(\frac{n \cdot \log m}{\log n}\big)$ and depth $O(\log n)$. This refines a classical result of Brent from 1974, according to which an arithmetical formula of size $n$ can be transformed into a logarithmic depth circuit of size $O(n)$., Comment: A short version of this paper appeared in the Proceedings of FSTTCS 2014

We study the complexity of algorithmic problems for matrices that are represented by multi-terminal decision diagrams (MTDD). These are a variant of ordered decision diagrams, where the terminal nodes are labeled with arbitrary elements of a semiring (instead of 0 and 1). A simple example shows that the product of two MTDD-represented matrices cannot be represented by an MTDD of polynomial size. To overcome this deficiency, we extended MTDDs to MTDD_+ by allowing componentwise symbolic addition of variables (of the same dimension) in rules. It is shown that accessing an entry, equality checking, matrix multiplication, and other basic matrix operations can be solved in polynomial time for MTDD_+-represented matrices. On the other hand, testing whether the determinant of a MTDD-represented matrix vanishes PSPACE$-complete, and the same problem is NP-complete for MTDD_+-represented diagonal matrices. Computing a specific entry in a product of MTDD-represented matrices is #P-complete., Comment: An extended abstract of this paper will appear in the Proceedings of CSR 2014

Unranked trees can be represented using their minimal dag (directed acyclic graph). For XML this achieves high compression ratios due to their repetitive mark up. Unranked trees are often represented through first child/next sibling (fcns) encoded binary trees. We study the difference in size (= number of edges) of minimal dag versus minimal dag of the fcns encoded binary tree. One main finding is that the size of the dag of the binary tree can never be smaller than the square root of the size of the minimal dag, and that there are examples that match this bound. We introduce a new combined structure, the hybrid dag, which is guaranteed to be smaller than (or equal in size to) both dags. Interestingly, we find through experiments that last child/previous sibling encodings are much better for XML compression via dags, than fcns encodings. We determine the average sizes of unranked and binary dags over a given set of labels (under uniform distribution) in terms of their exact generating functions, and in terms of their asymptotical behavior., Comment: A short version of this paper appeared in the Proceedings of ICDT 2013

A simple linear-time algorithm for constructing a linear context-free tree grammar of size O(rg + r g log (n/r g))for a given input tree T of size n is presented, where g is the size of a minimal linear context-free tree grammar for T, and r is the maximal rank of symbols in T (which is a constant in many applications). This is the first example of a grammar-based tree compression algorithm with a good, i.e. logarithmic in terms of the size of the input tree, approximation ratio. The analysis of the algorithm uses an extension of the recompression technique from strings to trees., Comment: 45 pages, published in Information and Computation. Approximation ratio improved since the first version, figures improved, some examples added. A small calculation error corrected since the previous version (all claims hold as previously)

We show that satisfiability for CTL* with equality-, order-, and modulo-constraints over Z is decidable. Previously, decidability was only known for certain fragments of CTL*, e.g., the existential and positive fragments and EF., Comment: To appear at Concur 2013