Implementation of some algorithms of combinatorial group theory in the algebraic programming system APS-1. (English. Russian original) Zbl 0835.20002
Cybern. Syst. Anal. 30, No. 6, 930-937 (1994); translation from Kibern. Sist. Anal. 6, 166-175 (1994).
We use the Nielsen algorithm as a base for the implementation of algorithms for some problems in the theory of free groups, semigroups, and finite algebras. The paper consists of three parts: the first part presents the necessary information from the theory of groups and finite automata; the second part sets out some problems of the theory of finitely generated free groups (semigroups) with the corresponding solution algorithms; and the third part considers the representation of finite algebras in the APS-1 system and algorithms to evaluate expressions in finite algebras.
MSC:
| 20-04 | Software, source code, etc. for problems pertaining to group theory |
| 68W30 | Symbolic computation and algebraic computation |
| 20F05 | Generators, relations, and presentations of groups |
| 20E05 | Free nonabelian groups |
| 20M05 | Free semigroups, generators and relations, word problems |
Keywords:
semigroups; Nielsen algorithm; implementation of algorithms; finite algebras; finite automata; finitely generated free groupsReferences:
| [1] | J. Calmet and J. A. Campbell (eds.), Artificial Intelligence and Symbolic Mathematical Computing, Int. Conf. AIMC-1, Karlsruhe, Germany, Aug. 3–6, 1992, Lect. Notes Comput. Sci., Vol. 737 (1992). |
| [2] | A. A. Letichevskii, A. B. Godlevskii, and S. L. Krivoi, ”An efficient algorithm to construct the basis of a subgroup of a free group,” Kibernetika, No. 3, 107–116 (1981). |
| [3] | A. A. Letichevskii and S. L. Krivoi, ”Implementation of the Nielsen algorithm in the algebraic programming system APS-1,” Kibern. Sistem. Anal., No. 5, 126–133 (1994). |
| [4] | W. Magnus, A. Karras, and D. Solitar, Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations, Wiley Interscience, New York (1966). · Zbl 0138.25604 |
| [5] | V. M. Glushkov, A. A. Letichevskii, and A. B. Godlevskii, Synthesis Methods for Discrete Models of Biological Systems [in Russian], Vol. 6, Vishcha Shkola, Kiev (1983). |
| [6] | A. A. Letichevsky, J. V. Kapitonova, and S. V. Konozenko, ”Computations in APS,” Informatica ’91, Franco-Soviet Symp.: Theoretical Computer Science and Methods of Compilation and Program Construction, Grenoble, Oct. 16–18 (1991), pp. 133–152. |
| [7] | S. L. Krivoi, ”An algorithm to construct the basis of the intersection of finitely generated free groups,” Kibernetika, No. 4, 4–10 (1982). |
| [8] | A. G. Kurosh, Group Theory [in Russian], Nauka, Moscow (1967). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
