ACC Seminar: Word Problems in HNN Extensions

ABSTRACT

This research investigates computational complexity aspects of word problems in HNN extensions. The study builds upon Miller’s classical result demonstrating the existence of HNN extensions with decidable word problems but undecidable conjugacy problems. The research primarily addresses three cases of HNN extensions with varying subgroup conditions:

(1) Ascending HNN extensions. We present Lohrey’s work on ascending HNN extensions, where he analyzed the computational complexity through reduction to compressed word problems;

(2) HNN extensions, where the associated subgroups are equal, normal in the free group, and of finite index; and

(3) the general case with distinct associated subgroups satisfying specific regularity conditions.

The methodology employs modern algorithmic tools including straight-line programs (SLPs), and graph techniques involving X regular subgroup graphs. For the case of equal normal subgroups of finite index, we demonstrate a polynomial-time algorithm using the unique properties of X-regular graphs.

BIOGRAPHY

Hanwen Shen is a Stevens Pure and Applied Mathematics Doctoral student. The research discussed in this talk was completed under the direction of Professor Alexander Ushakov.

Attendance: This is a technical talk open to all.
A campus map is available at https://tour.stevens.edu.
Additional information is available at https://web.stevens.edu/algebraic/.