Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T00:36:16.350Z Has data issue: false hasContentIssue false
  • English
  • Français

Some undecidable embedding problems for finite semigroups

Published online by Cambridge University Press:  20 January 2009

Marcel Jackson
Marcel Jackson
Affiliation:
Department of Mathematics, University of Tasmania, Hobart, Tasmania, Australia, E-mail address: [email protected]
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let S be a finite semigroup, A be a given subset of S and L, R, H, D and J be Green's equivalence relations. The problem of determining whether there exists a supersemigroup T of S from the class of all semigroups or from the class of finite semigroups, such that A lies in an L or R-class of T has a simple and well known solution (see for example [7], [8] or [3]). The analogous problem for J or D relations is trivial if T is of arbitrary size, but undecidable if T is required to be finite [4] (even if we restrict ourselves to the case |A| = 2 [6]). We show that for the relation H, the corresponding problem is undecidable in both the class of finite semigroups (answering Problem 1 of [9]) and in the class of all semigroups, extending related results obtained by M. V. Sapir in [9]. An infinite semigroup with a subset never lying in a H-class of any embedding semigroup is known and, in [9], the existence of a finite semigroup with this property is established. We present two eight element examples of such semigroups as well as other examples satisfying related properties.

Type
Research Article
Information
Proceedings of the Edinburgh Mathematical Society , Volume 42 , Issue 1 , February 1999 , pp. 113 - 125
Copyright
Copyright © Edinburgh Mathematical Society 1999

References

REFERENCES

1.Clifford, A. H. and Preston, G. B., The Algebraic Theory of Semigroups, Volumes 1, 2 (Amer. Math. Soc., Providence, RI, 1961, 1967).CrossRefGoogle Scholar
2.Fountain, J., Adequate semigroups, Proc. Edinburgh Math. Soc. 22 (1979), 113–125.Google Scholar
3.Fountain, J., Abundant semigroups, Proc. London Math. Soc 44 (1982), 103–129.CrossRefGoogle Scholar
4.Hall, T., Kublanovsky, S., Margolis, S., Sapir, M. and Trotter, P., Decidable and undecidable problems related to finite 0-simple semigroups, J Pure Appl. Algebra, to appear.Google Scholar
5.Kharlampovich, O. G. and Sapir, M. V., Algorithmic problems in varieties, Internat. J. Algebra Comput. 5 (1995), 379–602.Google Scholar
6.Kublanovsky, S. and Sapir, M. V., Potential divisibility in finite semigroups is undecidable, to appear (1996).Google Scholar
7.Lyapin, E. S., Semigroups (Translations of mathematical monographs Volume 3, Amer. Math. Soc., Providence, RI, 1974).Google Scholar
8.Pastijn, F., A representation of a semigroup by a semigroup of matrices over a group with zero, Semigroup Forum 10 (1975), 238–249.Google Scholar
9.Sapir, M. V., Eventually H-related sets and systems of equations over finite semigroups and rings, J. Algebra 183 (1996), 365–377.CrossRefGoogle Scholar