Tietze transformations with weighted substring search (Q1110650)

Implementations of Tietze transformations have been used both interactively and in the framework of simplification routines that follow certain strategies. They serve to find presentations with few generators and/or relations from given ones as well as to reduce presentations of subgroups of finite index in finitely presented groups that have been constructed by the Reidemeister-Schreier or the Modified Todd-Coxeter method. Because of the unsolvability of the word problem and related problems there is no ``best'' strategy for the simplification of presentations; each strategy follows certain heuristic rules as to which subwords to replace. The author reports about rather successful experiments with certain such rules influencing the elimination process by the assignment of weights to generators. A Tietze program in FORTRAN 77 incorporating these ideas is available from the author.