Search

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]

Powerful skew arithmetic circuits are introduced. These are skew arithmetic circuits with variables, where input gates can be labeled with powers x n for binary encoded numbers n. It is shown that polynomial identity testing for powerful skew arithmetic circuits belongs to c o R N C 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 c o R N C 2 ; this result is even new in the one-dimensional case, where the straight-line programs produce words. (ii) The compressed word problem (or circuit evaluation problem) for certain wreath products of finitely generated abelian groups belongs to c o R N C 2 . Using the Magnus embedding, it follows that the compressed word problem for a free metabelian group belongs to c o R N C 2 . [ABSTRACT FROM AUTHOR]

It is shown that there exist d, ℓ ≥ 3 and a sequence C1, ..., Cℓ of cyclic subgroups of the d-dimensional unitriangluar matrix group over ℤ (which is finitely generated nilpotent) such that membership in the product C1 C2 ⋯ Cℓ is undecidable. [ABSTRACT FROM AUTHOR]

It is shown that the compressed word problem of a graph product of finitely generated groups is polynomial time Turing-reducible to the compressed word problems of the vertex groups. A direct corollary of this result is that the word problem for the automorphism group of a right-angled Artin group or a right-angled Coxeter group can be solved in polynomial time. Moreover, it is shown that a restricted variant of the simultaneous compressed conjugacy problem is polynomial time Turing-reducible to the same problem for the vertex groups. A direct corollary of this result is that the word problem for the outer automorphism group of a right-angled Artin group or a right-angled Coxeter group can be solved in polynomial time. Finally, it is shown that the compressed variant of the ordinary conjugacy problem can be solved in polynomial time for right-angled Artin groups. [ABSTRACT FROM AUTHOR]

Membership problems for compressed strings in regular languages are investigated. Strings are represented by straight-line programs, i.e., context-free grammars that generate exactly one string. For the representation of regular languages, various formalisms with different degrees of succinctness (e.g., suitably extended regular expressions, hierarchical automata) are considered. Precise complexity bounds are derived. Among other results, it is shown that the compressed membership problem for regular expressions with intersection is PSPACE-complete. This solves an open problem of Plandowski and Rytter. [ABSTRACT FROM AUTHOR]

For monoids that satisfy a weak cancellation condition, it is shown that the decidability of the existential theory of word equations is preserved under graph products. Furthermore, it is shown that the positive theory of a graph product of groups can be reduced to the positive theories of those factors, which commute with all other factors, and the existential theories of the remaining factors. Both results also include suitable constraints for the variables. Larger classes of constraints lead in many cases to undecidability results. [ABSTRACT FROM AUTHOR]

Several transfer results for rational subsets and finitely generated subgroups of HNN-extensions G = 〈 H,t; t-1 at = φ(a) (a ∈ A) 〉 and amalgamated free products G = H *A J such that the associated subgroup A is finite. These transfer results allow to transfer decidability properties or structural properties from the subgroup H (resp. the subgroups H and J) to the group G. [ABSTRACT FROM AUTHOR]

Let G be a finitely generated virtually-free group. We consider the Birget–Rhodes expansion of G, which yields an inverse monoid and which is denoted by IM(G) in the following. We show that for a finite idempotent presentation P, the word problem of a quotient monoid IM(G)/P can be solved in linear time on a RAM. The uniform word problem, where G and the presentation P are also part of the input, is EXPTIME-complete. With IM(G)/P we associate a relational structure, which contains for every rational subset L of IM(G)/P a binary relation, consisting of all pairs (x,y) such that y can be obtained from x by right multiplication with an element from L. We prove that the first-order theory of this structure is decidable. This result implies that the emptiness problem for Boolean combinations of rational subsets of IM(G)/P is decidable, which, in turn implies the decidability of the submonoid membership problem of IM(G)/P. These results were known previously for free groups, only. Moreover, we provide a new algorithmic approach for these problems, which seems to be of independent interest even for free groups. We also show that one cannot expect decidability results in much larger frameworks than virtually-free groups because the subgroup membership problem of a subgroup H in an arbitrary group G can be reduced to a word problem of some IM(G)/P, where P depends only on H. A consequence is that there is a hyperbolic group G and a finite idempotent presentation P such that the word problem is undecidable for some finitely generated submonoid of IM(G)/P. In particular, the word problem of IM(G)/P is undecidable. [ABSTRACT FROM AUTHOR]

Cayley-graphs of monoids are investigated under a logical point of view. It is shown that the class of monoids, for which the Cayley-graph has a decidable monadic second-order theory, is closed under free products. This result is derived from a result of Walukiewicz, stating that the decidability of monadic second-order theories is preserved under tree-like unfoldings. Concerning first-order logic, it is shown that the class of monoids, for which the Cayley-graph has a decidable first-order theory, is closed under arbitrary graph products, which generalize both, free and direct products. For the proof of this result, tree-like unfoldings are generalized to so-called factorized unfoldings. It is shown that the decidability of the first-order theory of a structure is preserved by factorized unfoldings. Several additional results concerning factorized unfoldings are shown. [ABSTRACT FROM AUTHOR]

Several complexity and decidability results for automatic monoids are shown: (i) there exists an automatic monoid with a P-complete word problem, (ii) there exists an automatic monoid such that the first-order theory of the corresponding Cayley-graph is not elementary decidable, and (iii) there exists an automatic monoid such that reachability in the corresponding Cayley-graph is undecidable. Moreover, it is shown that for every hyperbolic group the word problem belongs to LOGCFL, which improves a result of Cai [8]. [ABSTRACT FROM AUTHOR]

Based on a PSPACE-completeness result for free monoids with involution [4] it is shown that the existential theory of equations with rational constraints in plain groups is PSPACE-complete. As a corollary this settles a question from [16]. [ABSTRACT FROM AUTHOR]