Narrow Results

We discuss time complexity of the Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group.

A group is called HNN-free if it has no subgroups that are nontrivial HNN-extensions. We prove that finitely generated HNN-free implies virtually polycyclic for a large class of groups. We also consider finitely generated groups with no free subsemigroups of rank 2 and show that in many situations such groups are virtually nilpotent. Finally, as an application of our results, we determine the structure of locally graded groups in which every subgroup is pronormal, thus generalizing a theorem of Kuzennyi and Subbotin.

We give necessary and sufficient conditions in order that lower bounded HNN-extensions of inverse semigroups and HNN-extensions of finite inverse semigroups are completely semisimple semigroups. Since it is well known that an inverse semigroup is completely semisimple if and only if it does not contain a copy of the bicyclic semigroup, we first characterize such HNN-extensions containing a bicyclic subsemigroup making use of the special feature of their Schützenberger automata.

In this paper, we prove that two-generator one-relator groups with depth less than or equal to 3 can be effectively embedded into a tower of HNN-extensions in which each group has the effective standard normal form. We give an example to show how to deal with some general cases for one-relator groups. By using the Magnus method and Composition-Diamond Lemma, we reprove the Higman-Neumann-Neumann embedding theorem.

In this survey article, we report some new results of Gröbner-Shirshov bases, including new Composition-Diamond lemmas, applications of some known Composition-Diamond lemmas and content of some expository papers.