Generic complexity of the word problem in some semigroups. (English. Russian original) Zbl 07786478
Algebra Logic 61, No. 6, 524-536 (2023); translation from Algebra Logika 61, No. 6, 766-783 (2022).
In solving word problems for various structures, generic algorithms are algorithms that provide solutions for almost all inputs, outputting an indefinite answer for other rare inputs. In this paper, the authors show that the word problem in a certain class of semigroups is generically decidable. This class consists of finitely generated semigroups \(S\) and for which there exists a congruence \(\theta\) such that the quotient semigroup \(S/\theta\) is an infinite residually finite monoid with cancellation property and has a decidable word problem.
MSC:
| 20M05 | Free semigroups, generators and relations, word problems |
References:
| [1] | Markov, AA, Impossibility of some algorithms in associative systems, Dokl. Akad. Nauk SSSR, 55, 7, 587-590 (1947) |
| [2] | Post, EL, Recursive unsolvability of a problem of Thue, J. Symb. Log., 12, 1, 1-11 (1947) · Zbl 1263.03030 · doi:10.2307/2267170 |
| [3] | Novikov, PS, On the algorithmic unsolvability of the word problem in group theory, Tr. MIAN SSSR, 44, 3-143 (1955) |
| [4] | Tseitin, GS, An associative calculus with an insoluble problem of equivalence, Tr. MIAN SSSR, 52, 172-189 (1958) · Zbl 0087.25303 |
| [5] | Makanin, GS, On the identity problem in finitely defined semigroups, Dokl. Akad. Nauk SSSR, 171, 2, 285-287 (1966) · Zbl 0189.30204 |
| [6] | Matiyasevich, YuV, Simple examples of unsolvable canonical calculi, Tr. MIAN SSSR, 93, 50-88 (1967) · Zbl 0193.31801 |
| [7] | I. Kapovich, A. Myasnikov, P. Schupp, and V. Shpilrain, “Generic-case complexity, decision problems in group theory, and random walks,” J. Alg., 264, No. 2, 665-694 (2003). 8. W. Woess, “Cogrowth of groups and simple random walks,” Arch. Math., 41, 363-370 (1983). · Zbl 1041.20021 |
| [8] | L. Bartholdi, “Counting paths in graphs,” Enseign. Math., II. Sér., 45, Nos. 1/2, 83-131 (1999). · Zbl 0961.05032 |
| [9] | R. I. Grigorchuk, “Symmetrical random walks on discrete groups,” in Adv. Probab. Related Topics, 6, Marcel Dekker, New York (1980), pp. 285-325. · Zbl 0475.60007 |
| [10] | D. Won, “Word problems on balanced semigroups and balanced groups,” City Univ. New York, ProQuest Disser. Publ., 3296964 (2008). |
| [11] | S. I. Adyan and V. G. Durnev, “Decision problems for groups and semigroups,” Usp. Mat. Nauk, 55, No. 2,(332) 3-94 (2000). · Zbl 0958.20029 |
| [12] | Nyberg-Brodda, C-F, The word problem for one-relation monoids: a survey, Semigroup Forum, 103, 2, 297-355 (2021) · Zbl 1508.20068 · doi:10.1007/s00233-021-10216-8 |
| [13] | A. Rybalov, “A generic algorithm for the word problem in semigroups and groups,” J. Phys.: Conf. Ser., Proc. Theor. Comp. Sci., Sect. of IV Int. Sci. Conf. “Mechanical Science and Technology Update,”1546 (012100) (2020), pp. 1-10. |
| [14] | Rybalov, AN, A generic algorithm for the word problem in some semigroups, Vestnik Omsk Univ., 26, 1, 16-20 (2021) |
| [15] | D. Hirschfeldt, “Some questions in computable mathematics,” in Lect. Notes Comput. Sci., 10010, Springer, Cham (2017), pp. 22-55. · Zbl 1480.03006 |
| [16] | A. Meyer, “An open problem on creative sets,” Recurs. Funct. Th. Newsletter, 4, 15/16 (1973). |
| [17] | A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Vol. 1, Math. Surv., 7, Am. Math. Soc., Providence, RI (1961). · Zbl 0111.03403 |
| [18] | Feller, W., An Introduction to Probability Theory and Its Applications (1960), New York: Wiley, New York · Zbl 0158.34902 |
| [19] | A. I. Mal’tsev, “Homomorphisms onto finite groups,” Uch. Zap. Ivanov. Ped. Inst., 18, No. 5, 49-60 (1958). |
| [20] | Myasnikov, AG; Rybalov, AN, Generic complexity of undecidable problems J, . Symb. Log., 73, 2, 656-673 (2008) · Zbl 1140.03025 · doi:10.2178/jsl/1208359065 |
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.
