Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-28T15:13:59.988Z Has data issue: false hasContentIssue false
  • English
  • Français

Undecidability of the identity problem for finite semigroups

Published online by Cambridge University Press:  12 March 2014

Douglas Albert ,
Robert Baldinger  and
John Rhodes
Douglas Albert
Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720
Robert Baldinger
Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720, E-mail: [email protected]
John Rhodes
Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

In 1947 E. Post [28] and A. A. Markov [18] independently proved the undecidability of the word problem (or the problem of deducibility of relations) for semigroups. In 1968 V. L. Murskil [23] proved the undecidability of the identity problem (or the problem of deducibility of identities) in semigroups.

If we slightly generalize the statement of these results we can state many related results in the literature and state our new results proved here. Let V denote either a (Birkhoff) variety of semigroups or groups or a pseudovariety of finite semigroups. By a very well-known theorem a (Birkhoff) variety is defined by equations or equivalently closed under substructure, surmorphisms and all products; see [7]. It is also well known that V is a pseudovariety of finite semigroups iff V is closed under substructure, surmorphism and finite products, or, equivalently, determined eventually by equations w1 = w1′, w2 = w2′, w3 = w3′,… (where the finite semigroup S eventually satisfies these equations iff there exists an n, depending on S, such that S satisfies Wj = Wj′ for j ≥ n). See [8] and [29]. All semigroups form a variety while all finite semigroups form a pseudovariety.

We now consider a table (see the next page). In it, for example, the box denoting the “word” (identity) problem for the psuedovariety V” means, given a finite set of relations (identities) E and a relation (identity) u = ν, the problem of whether it is decidable that E implies u = ν inside V.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 57 , Issue 1 , March 1992 , pp. 179 - 192
Copyright
Copyright © Association for Symbolic Logic 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Albert, D. and Rhodes, J., Undecidability of the identity problem for finite semigroups with applications, preprint, 1986.Google Scholar
[2]Almeida, J., Recent developments in the theory of implicit operations, Monoids and semigroups with applications (proceedings of the Berkeley workshop on monoids; Rhodes, J., editor), World Scientific Publishing, Singapore, 1991, pp. 105–117.Google Scholar
[3]Baumslag, G., Gildenhuys, D., and Strebel, R., Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I, Journal of Pure and Applied Algebra, vol. 39 (1986), pp. 53–94.CrossRefGoogle Scholar
[4]Bean, D. R., Ehrenfeucht, A., and McNulty, G. F., Avoidable patterns in strings of symbols, Pacific Journal of Mathematics, vol. 85 (1979), 261–294.CrossRefGoogle Scholar
[5]Boone, W. W., Certain simple, unsolvable problems of group theory. I-VI, Indagationes Mathematicae, vol. 16(1954), pp. 231–237, 492–497; vol. 17(1955), pp. 252–256, 571–577; vol. 19(1957), pp. 22–27, 227–232.CrossRefGoogle Scholar
[6]Britten, J. L., The word problem for groups, Proceedings of the London Mathematical Society, ser. 3, vol. 8 (1958), pp. 493–506.CrossRefGoogle Scholar
[7]Burris, S. and Sankappanavar, H. P., A course in universal algebra, Springer-Verlag, Berlin, 1980.Google Scholar
[8]Eilenberg, S., Automata, languages and machines. Vol. B, Academic Press, New York, 1976.Google Scholar
[9]Evans, T., The lattice of semigroup varieties, Semigroup Forum, vol. 2 (1971), pp. 1–43.CrossRefGoogle Scholar
[10]Gurevich, Y., The word problem for certain classes of semigroups, Algebra i Logika Seminar, vol. 5 (1966), no. 5, pp. 25–35. (Russian)Google Scholar
[11]Gurevich, Y. and Lewis, H. R., The word problem for cancellation semigroups with zeros, this Journal, vol. 49 (1984), pp. 184–191.Google Scholar
[12]Jones, G., Varieties and simple groups, Journal of the Australian Mathematical Society, vol. 17 (1974), pp. 163–173.CrossRefGoogle Scholar
[13]Kharlampovich, O. G., Algorithmic and other combinatorial problems for groups and Lie algebras, Ph. D. thesis, Department of Mathematics, Ural State University, Sverdlovsk, 1983. (Russian).Google Scholar
[14]Kharlampovich, O. G., A finitely presented solvable group with insoluble word problem, Izvestiya Akademii Nauk SSSR Seriya Matematicheskaya, vol. 45 (1981), pp. 852–873; English translation, Mathematics of the USSR Izvestiya, vol. 19 (1982), pp. 151–169.Google Scholar
[15]Kleǐman, Yu. G., Identities and some algorithmic problems in groups, Doklady Akademii Nauk SSSR, vol. 244 (1979), pp. 814–818; English translation, Soviet Mathematics Doklady, vol. 20 (1979), pp. 115–119.Google Scholar
[16]Mal'cev, A. I., Identity relations in varieties of quasigroups, Matematicheskiǐ Sbornik, vol. 69 (111) (1966), pp. 3–12; English translation, American Mathematical Society Translations, ser. 2, vol. 82 (1969), pp. 225-235.Google Scholar
[17]Mal'cev, A. I., On homomorphisms onto finite groups, Ivanovskiǐ Gosudarstvennyǐ Pedagogicheskiǐ Institut Uchenye Zapiski, vol. 18 (1958), pp. 49–60; English translation, American Mathematical Society Translations, ser. 2, vol. 119 (1983), pp. 67–79.Google Scholar
[18]Markov, A. A., On the impossibility of certain algorithms in the theory of associative systems, Doklady Akademii Nauk SSSR, vol. 55 (1947), pp. 587–590; English translation, Comptes Rendus (Doklady) de l'Académie des Sciences de l'URSS, vol. 55 (1947), pp. 583–586.Google Scholar
[19]Mel'nichuk, I. L., Unsolubility of the problem of equality and divisibility in certain varieties of semigroups, Algebra i Logika, vol. 23 (1984), pp. 430–438; English translation, Algebra and Logic, vol. 23 (1984), pp. 297–302.Google Scholar
[20]Mel'nichuk, I. L., Sapir, M. V., and Kharlampovich, O. G., Word problems in varieties of semigroups, rings and Lie algebras, Sibirskiǐ Matematicheskiǐ Zhurnal, vol. 27 (1986), no. 6, pp. 144–156; English translation, Siberian Mathematical Journal, vol. 27 (1986), pp. 904-919.Google Scholar
[21]Minsky, M. L., Recursive unsolvability of Post's problem of “tag” and other topics in the theory of Turing machines, Annals of Mathematics, ser. 2, vol. 74 (1961), pp. 437–455.CrossRefGoogle Scholar
[22]Morse, M. and Hedlund, G. A., Unending chess, symbolic dynamics and a problem in semigroups, Duke Mathematical Journal, vol. 11 (1944), pp. 1–7.CrossRefGoogle Scholar
[23]Murskiǐ, V. L., Some examples of varieties of semigroups, Matematicheskie Zametki, vol. 3 (1968), pp. 663–670; English translation, Mathematical Notes, vol. 3 (1968), pp. 423-427.Google Scholar
[24]Neumann, H., Varieties of groups, Springer-Verlag, Berlin, 1967.CrossRefGoogle Scholar
[25]Novikov, P. S., On the algorithmic unsolubility of the word problem in group theory, Trudy Matematicheskogo Instituta imeni V. A. Steklova, vol. 44 (1955); English translation, American Mathematical Society Translations, ser. 2, vol. 9 (1958), pp. 1–122.Google Scholar
[26]Oates, S. and Powell, M. B., Identical relations in finite groups, Journal of Algebra, vol. 1 (1964), pp. 11–39.CrossRefGoogle Scholar
[27]Pin, J.-E., Variétés de langages formels, Masson, Paris, 1984; English translation, North Oxford Academy, Oxford, and Plenum, New York, 1986.Google Scholar
[28]Post, E., Recursive unsolvability of a problem of Thue, this Journal, vol. 12 (1947), pp. 1–11.Google Scholar
[29]Reiterman, J., The Birkhoff problem for finite algebras, Algebra Universalis, vol. 14 (1982), pp. 1–10.CrossRefGoogle Scholar
[30]Rhodes, J., The presentation lemma for complexity of finite semigroups, unpublished manuscript, 1974.Google Scholar
[31]Rhodes, J., Global structure theorems for arbitrary semigroups, Proceedings of the Marquette conference on semigroups (Byleen, K.et al., editors), Department of Mathematics, Marquette University, Milwaukee, Wisconsin, 1984, pp. 197–228.Google Scholar
[32]Rhodes, J., New techniques in global semigroup theory, Semigroups and their applications (Goberstein, S. M. and Higgins, P. M., editors), Reidel, Dordrecht, 1987, pp. 169–182.CrossRefGoogle Scholar
[33]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[34]Sapir, M. V., Weak word problem for finite semigroups, Semigroups and monoids with applications (proceedings of the Berkeley workshop on monoids; Rhodes, J., editor), World Scientific Publishing, Singapore, 1991, pp. 206–219.Google Scholar
[35]Sapir, M. V., Algorithmic problems in semigroup varieties, Algebra i Logika, vol. 27 (1988), pp. 440–463; English translation, Algebra and Logic, vol. 27 (1988), pp. 275–292.Google Scholar
[36]Sapir, M. V., private communication.Google Scholar
[37]Slobodskoǐ, A. M., Undecidability of the universal theory of finite groups, Algebra i Logika, vol. 20 (1981), pp. 207–230; English translation, Algebra and Logic, vol. 20 (1981), pp. 139–156.Google Scholar
[38]Shevrin, L. N. and Volkov, M. V., Identities of semigroups, Izvestiya Vysshikh Uchebnykh Zavedeniǐ Matematika 1985, no. 11 (282), pp. 3–47; English translation, Soviet Mathematics (Iz. VVZ), vol. 29 (1985), no. 11, pp. 1–64.Google Scholar
[39]Tilson, B., Categories as algebra, an essential ingredient in the theory of monoids, Journal of Pure and Applied Algebra, vol. 48 (1987), pp. 83–198.CrossRefGoogle Scholar
[40]Weil, P., Implicit operations on pseudo-varieties: an introduction, Semigroups and monoids with applications (proceedings of the Berkeley workshop on monoids; Rhodes, J., editor), World Scientific Publishing, Singapore, 1991, pp. 89–104.Google Scholar