Implementation of the Nielsen algorithm in the algebraic programming system APS-1 (Q1905209)

Nielsen's algorithm in the theory of finitely generated free groups has many important applications. Efficient implementation of this algorithm by both speed (time) and computer resources (memory) is therefore a relevant topic. The construction of an efficient Nielsen algorithm has been considered elsewhere. The available implementations of this algorithm in particular programming languages are procedural and have good time characteristics. In this paper, the Nielsen algorithm is implemented as a system of rewriting rules (which corresponds to the functional style of programming) utilizing the capabilities of the algebraic programming system APS-1. This implementation uses two basic systems of relationships -- a system for the construction of an irreducible word in a group (the construction of a canonical form of an element in a free group) and a system for the implementation of a nonascending sequence of Nielsen reductions (i.e., the Nielsen reduction process is proper). The main question is that of relative efficiency of the proposed functional implementation compared to the procedural versions of the Nielsen algorithm. The time characteristics of our functional implementation are comparable with the procedural implementation of the Nielsen algorithm in C, which was used as a benchmark.