zbMATH — the first resource for mathematics

The parallel complexity of some constructions in combinatorial group theory. (English) Zbl 0698.68053
Summary: The parallel complexity of several important constructions in combinatorial group theory is studied. direct and free products, special HNN-extensions, extensions by finite groups, and wreath products are investigated. \(NC^ 1\)-equivalences between the complexity of the result on the one hand and the complexity of the elements of these constructions on the other hand are proved.

68Q25 Analysis of algorithms and problem complexity
20F05 Generators, relations, and presentations of groups
20D60 Arithmetic and combinatorial problems involving abstract finite groups
68W30 Symbolic computation and algebraic computation