Search

The power word problem for a group G asks whether an expression u 1 x 1 ⋯ 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 uNC 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 C without order two elements, the uniform power word problem in a graph product can be solved in AC 0 [ C = L UPowWP (C) ] , where UPowWP (C) denotes the uniform power word problem for groups from the class 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 (Lohrey and Weiß 2019b, Stober and Weiß 2022a). In Stober and Weiß (2022a) 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 in Stober and Weiß (2022a) is true, our proof relies on this additional assumption. [ABSTRACT FROM AUTHOR]

In the sliding window streaming model the goal is to compute an output value that only depends on the last n symbols from the data stream. Thereby, only space sublinear in the window size n should be used. Quite often randomization is used in order to achieve this goal. In the literature, one finds two different correctness criteria for randomized sliding window algorithms: (i) one can require that for every data stream and every time instant t, the algorithm computes a correct output value with high probability, or (ii) one can require that for every data stream the probability that the algorithm computes at every time instant a correct output value is high. Condition (ii) is stronger than (i) and is called "strict correctness" in this paper. The main result of this paper states that every strictly correct randomized sliding window algorithm can be derandomized without increasing the worst-case space consumption. [ABSTRACT FROM AUTHOR]

We introduce forest straight-line programs (FSLPs for short) 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 and/or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees. An extended abstract of this paper appeared in Gascóon et al. (2018). [ABSTRACT FROM AUTHOR]

A linear space data structure for grammar-compressed trees is presented which allows to carry out tree traversal operations and subtree equality checks in constant time. A traversal step consists of moving to the parent or to the ith child of a node. [ABSTRACT FROM AUTHOR]

We study the circuit evaluation problem (also known as the compressed word problem) for finitely generated linear groups. The best upper bound for this problem is coRP (the complements of problems in randomized polynomial time), which is shown by a reduction to polynomial identity testing for arithmetic circuits. Conversely, the compressed word problem for the linear group SL3(Z) is equivalent to polynomial identity testing. In the paper, we show that the compressed word problem for every finitely generated nilpotent group is in DET ⊆ NC2.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. It is a major open problem, whether polynomial identity testing for skew arithmetic circuits can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

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 may 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 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. These problems can be still solved in polynomial time for TSLPs. [ABSTRACT FROM AUTHOR]

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 every graph group. This result even holds if the group elements are represented in a compressed form by so called straight-line programs, which generalizes the classical NP-completeness result of the integer knapsack problem. If group elements are represented explicitly by words over the generators, then knapsack for a graph group belongs to the class LogCFL (a subclass of P) if the graph group can be built up from the trivial group using the operations of free product and direct product with $\mathbb {Z}$ . In all other cases, the knapsack problem is NP-complete. [ABSTRACT FROM AUTHOR]

It is shown that the subgroup membership problem for a virtually free group can be decided in polynomial time when all group elements are represented by so-called power words, i.e., words of the form p1z1p2z2⋯pkzk\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$p_1^{z_1} p_2^{z_2} \cdots p_k^{z_k}$$\end{document}. Here the pi\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$p_i$$\end{document} are explicit words over the generating set of the group and all zi\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$z_i$$\end{document} are binary encoded integers. As a corollary, it follows that the subgroup membership problem for the matrix group GL(2,Z)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\textsf{GL}(2,\mathbb {Z})$$\end{document} can be decided in polynomial time when elements of GL(2,Z)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\textsf{GL}(2,\mathbb {Z})$$\end{document} are represented by matrices with binary encoded integers. For the same input representation, it also shown that one can compute in polynomial time the index of a given finitely generated subgroup of GL(2,Z)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\textsf{GL}(2,\mathbb {Z})$$\end{document}. [ABSTRACT FROM AUTHOR]

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 + MTDDs 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 is P S P A C E-complete, and the same problem is N P-complete for + MTDD-represented diagonal matrices. Computing a specific entry in a product of MTDD-represented matrices is # P-complete. [ABSTRACT FROM AUTHOR]

Recently, we have shown that satisfiability for the temporal logic E C T L with local constraints over (ℤ, <, =) is decidable using a new technique (Carapelle et al., 2013). This approach reduces the satisfiability problem of E C T L with constraints over some structure $\mathcal {A}$ (or class of structures) to the problem whether $\mathcal {A}$ has a certain model theoretic property that we called EHD (for 'existence of homomorphisms is definable'). Here we apply this approach to structures that are tree-like and obtain several results. We show that satisfiability of E C T L 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-Fraïssé-games for W M S O + B (weak M S O with the bounding quantifier) and use them to show that the infinite (order) tree does not have the EHD-property. As a consequence, our technique cannot be used to establish whether satisfiability of E C T L with constraints over the infinite (order) tree is decidable. A preliminary version of this paper has appeared as (Carapelle et al., 2015). [ABSTRACT FROM AUTHOR]

We study what languages can be constructed from a non-regular language L using Boolean operations and synchronous or non-synchronous rational transductions. If all rational transductions are allowed, one can construct the whole arithmetical hierarchy relative to L. In the case of synchronous rational transductions, we present non-regular languages that allow constructing languages arbitrarily high in the arithmetical hierarchy and we present non-regular languages that allow constructing only recursive languages. A consequence of the results is that aside from the regular languages, no full trio generated by a single language is closed under complementation. Another consequence is that there is a fixed rational Kripke frame such that assigning an arbitrary non-regular language to some variable allows the definition of any language from the arithmetical hierarchy in the corresponding Kripke structure using multimodal logic. [ABSTRACT FROM AUTHOR]

Unranked node-labeled 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. [ABSTRACT FROM AUTHOR]