Search

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. [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]

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]

Abstract: In this paper we show that the membership problems for finitely generated submonoids and for rational subsets are recursively equivalent for groups with two or more ends. [Copyright &y& Elsevier]

Free partially commutative inverse monoids are investigated. As in the case of free partially commutative monoids or groups ( trace monoids or graph groups), free partially commutative inverse monoids are defined as quotients of free inverse monoids modulo a partially defined commutation relation on the generators. A quasi linear time algorithm for the word problem is presented. More precisely, we give an $\mathcal {O}(n\log(n))$ algorithm for a RAM. $\mathsf {NP}$ -completeness of the submonoid membership problem (also known as the generalized word problem) and the membership problem for rational sets is shown. Moreover, free partially commutative inverse monoids modulo a finite idempotent presentation are studied. It turns out that the word problem is decidable if and only if the complement of the partial commutation relation is transitive. [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]

Those graph products of groups that are virtually-free are characterized. [ABSTRACT FROM AUTHOR]

We prove that the first-order theory of the one-step rewriting relation associated with a trace rewriting system is decidable but in general not elementary. This extends known results on semi-Thue systems but our proofs use new methods; these new methods yield the decidability of local properties expressed in first-order logic augmented by modulo-counting quantifiers. Using the main decidability result, we define several subclasses of trace rewriting systems for which the confluence problem is decidable. [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]