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

DOI10.1007/BF02367756MaRDI QIDQ1905209zbMATH OpenFDO

Authors Yanyan Li

Publication date 8 February 1996

Published in Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02367756

zbMATH Keywords

canonical formsfinitely generated free groupsirreducible wordsNielsen reduction processNielsen's algorithmrewriting rules

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to group theory (20-04) Free nonabelian groups (20E05) Generators, relations, and presentations of groups (20F05) Symbolic computation and algebraic computation (68W30)

Review text

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.

Recommendations

• Implementation of some algorithms of combinatorial group theory in the algebraic programming system APS-1
• Algorithms for implementation of solutions of systems of linear algebraic equations
• scientific article; zbMATH DE number 1273691
• An approximate algorithm for nonlinear integer programming
• An approximate algorithm for nonlinear integer programming
• Application of a structured LISP system to computer algebra
• Computational algebra with APL
• A partial enumeration algorithm for pure nonlinear integer programming

Cited in

(3)

• APS-1
• Implementation of some algorithms of combinatorial group theory in the algebraic programming system APS-1
• Efficiency of certain algorithms of combinatorial group theory

Describes a project that uses

Uses Software

• APS

This page was built for publication: Implementation of the Nielsen algorithm in the algebraic programming system APS-1

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1905209)