Search

We show that a context-free grammar of sizem that produces a single string w of length n (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar forw of size O(m), whose unique derivation tree has depth O(logn). This solves an open problem in the area of grammar-based compression, improves many results in this area, and greatly simplifies many existing constructions. Similar results are shown for two formalisms for grammar-based tree compression: top dags and forest straight-line programs. These balancing results can be 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 O(logn) with the cost of a constant multiplicative size increase. Here, n refers to the size of the unfolding (or unravelling) of the circuit. In particular, this results applies to standard arithmetic circuits over (noncommutative) semirings. [ABSTRACT FROM AUTHOR]

We prove that the power word problem for certain metabelian subgroups of G L (2 , ℂ) (including the solvable Baumslag–Solitar groups BS (1 , q) = 〈 a , t | t a t − 1 = a q 〉) belongs to the circuit complexity class T C 0 . In the power word problem, the input consists of group elements g 1 , ... , g d and binary encoded integers n 1 , ... , n d and it is asked whether g 1 n 1 ⋯ g d n d = 1 holds. Moreover, we prove that the knapsack problem for BS (1 , q) is N P -complete. In the knapsack problem, the input consists of group elements g 1 , ... , g d , h and it is asked whether the equation g 1 x 1 ⋯ g d x d = h has a solution in ℕ 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 BS (1 , q). [ABSTRACT FROM AUTHOR]

The study investigates the application of first-order logic for automatic structures to structures with an injectively omega-automatic presentation.

The definition of $\text {k}^{th}$ -order empirical entropy of strings is extended to node-labelled binary trees: A notion of $\text {k}^{th}$ -order empirical entropy for node-labelled binary trees is proposed that is able to capture regularities in both labels and structure of a tree. 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 $\text {k}^{th}$ -order empirical entropy plus some lower order terms. This result is then extended from node-labelled binary trees to node-labelled unranked trees. This generalizes recent results for grammar-based string compression to grammar-based tree compression. Additionally, experimental results with real XML document trees are presented, in which the proposed notion of $\text {k}^{th}$ -order empirical tree entropy is computed and compared to the performance of grammar-based tree compressors for those XML document trees. [ABSTRACT FROM AUTHOR]

A family of tree automata of size n is presented such that the size of the largest common prefix (lcp) tree of all accepted trees is exponential in n. Moreover, it is shown that this prefix tree is not compressible via DAGs (directed acyclic graphs) or tree straight-line programs. We also show that determining whether or not the lcp trees of two given tree automata are equal is coNP-complete; the result holds even for deterministic bottom-up tree automata accepting finite tree languages. These results are in sharp contrast to the case of context-free string grammars. [ABSTRACT FROM AUTHOR]