Abstract: Over the past 20-25 years, a fruitful connection has emerged between group theory and computer science. Significant attention began to be paid to the algorithmic problems of group theory in view of their open applications. In addition to the traditional questions of solvability, the questions of complexity and effective solvability began to be studied. This paper provides a brief overview of this area. Attention is drawn to algorithmic problems related to rational subsets of groups which are a natural generalization of regular sets. The submonoid membership problem for free nilpotent groups, which has attracted the attention of a number of researchers in recent years, is considered. It is shown how the apparatus of subsets of positive elements makes it possible to obtain sufficient conditions for the solvability of this problem in the case of nilpotency class two. Note that the author announced a negative solution to this problem for a free nilpotent group of nilpotency class at least two of sufficiently large rank (the full proof is in print). This gives an answer to the well-known question of Lohrey-Steinberg about the existence of a finitely generated nilpotent group with an unsolvable submonoid membership problem. In view of this result, finding sufficient conditions for the solvability of this problem for nilpotent groups of class two is an urgent problem.

Cite: Roman’kov V.A.
POSITIVE ELEMENTS AND SUFFICIENT CONDITIONS FOR SOLVABILITY OF THE SUBMONOID MEMBERSHIP PROBLEM FOR NILPOTENT GROUPS OF CLASS TWO
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2022. V.19. N1. P.387-403. DOI: 10.33048/semi.2022.19.034 WOS Scopus РИНЦ

Identifiers:

Web of science:	WOS:000886649700012
Scopus:	2-s2.0-85134546702
Elibrary:	49384645

Citing:

DB	Citing
Scopus	3
Web of science	3
Elibrary	6

Altmetrics: