Implementation of the Nielsen algorithm in the algebraic programming system APS-1 (Q1905209): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:12, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Implementation of the Nielsen algorithm in the algebraic programming system APS-1 |
scientific article |
Statements
Implementation of the Nielsen algorithm in the algebraic programming system APS-1 (English)
0 references
8 February 1996
0 references
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.
0 references
Nielsen's algorithm
0 references
finitely generated free groups
0 references
rewriting rules
0 references
irreducible words
0 references
canonical forms
0 references
Nielsen reduction process
0 references