HNN extensions of free groups with equal associated subgroups of finite index: polynomial time word problem

2025/10/04 by Shen, Hanwen, Alexander Ushakov, Ushakov, Alexander
Mathematics · Computer Science · #Geometric and Algebraic Topology #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2510.03801

Abstract

Let G=F∗_φt be an HNN extension of a free group F with two equal associated normal subgroups H₁ = H₂ of finite index. We prove that the word problem in G is decidable in polynomial time. This result extends to the case where the subgroups H₁=H₂ are not normal, provided that the isomorphism φ:H₁→ H₂ satisfies an additional condition described in Section 5.

Citations

• Complexity of word problems for HNN-extensions
• Compressed word problems in HNN-extensions and amalgamated products
• Generic complexity of the Conjugacy Problem in HNN-extensions and algorithmic stratification of Miller's groups

Related

• Complexity of word problems for HNN-extensions
• Compressed word problems in HNN-extensions and amalgamated products
• Embedding Partial HNN Extensions In Ascending HNN Extensions
• On the submonoid membership problem for HNN extensions of free groups
• Failure of the finitely generated intersection property for ascending HNN extensions of free groups