Compressed word problems in HNN-extensions and amalgamated products (Q639849): Difference between revisions

In the compressed word problem for a group \(G\), the input word over the generators is not given explicitly but succinctly via a so called straight line program. This is a context free grammar that generates exactly one word. For a (base) group \(H\) with two isomorphic subgroups \(A\) and \(B\) and an isomorphism \(\varphi:A\rightarrow B\), the HNN-extension (HNN for Higman, Neumann, and Neumann) is the group \[ G=\langle H,t\mid \forall a \in A : t^{-1}at=\varphi(a)\rangle. \] The subgroups \(A\) and \(B\) are called the associated subgroups. The amalgamated free product of two groups \(H_1\) and \(H_2\) with isomorphic subgroups \(A_1 \leq H_1,A_2 \leq H_2\) and an isomorphism \(\varphi:A_1\rightarrow A_2\), is the group \[ G=\langle H_1\ast H_2\mid \forall a \in A_1 : a=\varphi(a)\rangle. \] Two classical facts about these notions are: (1) a group has more than one end if and only if it is either an HNN-extension with finite associated subgroups or an amalgamated free product with finite identified subgroups [\textit{J. R. Stallings}, Group theory and three-dimensional manifolds.Yale Mathematical Monographs. 4. New Haven-London: Yale University Press (1971; Zbl 0241.57001)]; and (2) a group is virtually free (i.e., has a free subgroup of finite index) if and only if it can be built up from finite groups using amalgamated products with finite identified subgroups and HNN-extensions with finite associated subgroups [\textit{W. Dicks} and \textit{M. J. Dunwoody}, Groups acting on graphs. Cambridge Studies in Advanced Mathematics, 17. Cambridge etc.: Cambridge University Press (1989; Zbl 0665.20001)]. The word problem for an HNN-extension with finite associated groups can be reduced in polynomial time to the word problem of the base group. The main result of the paper is generalizing the above transfer theorem to the compressed word problem (instead of the usual word problem). The authors prove a bit more, in the sense that they consider multiple HNN-extensions: for a base group \(H\) and a natural number \(n\), and partial isomorphisms \(\varphi_i:A\rightarrow B\) for \(i=1,\dots,n\) and for fixed finite subgroups \(A,B \leq H\), the multiple HNN-extension is the group \[ G=\langle H,t_1,\dots,t_n\mid \forall a \in \text{dom}(\varphi_i) \forall i \leq n : t_i^{-1}at_i=\varphi_i(a)\rangle. \] It is also shown that the compressed word problem for an amalgamated free product \[ \langle H_1\ast H_2\mid \forall a \in A_1 : a=\varphi(a)\rangle \] with finite \(A_1\) can be reduced in polynomial time to the compressed word problems of \(H_1\) and \(H_2\).