Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-29T03:31:14.679Z Has data issue: false hasContentIssue false
  • English
  • Français

The pseudoidentity problem and reducibility for completely regular semigroups

Published online by Cambridge University Press:  17 April 2009

Jorge Almedia  and
Peter G. Trotter
Jorge Almedia
Affiliation:
Centro de Matemática, Universidade de Porto, P. Gomes Teixeira, 4099–002 Porto, Portugal
Peter G. Trotter
Affiliation:
Department of Mathematics, University of Tasmania, GPO Box 252–37, Hobart, Tas. 7001, Australia
Rights & Permissions [Opens in a new window]

Abstract

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.

Dedicated to George Szekeres on the occasion of his 90th birthday

Necessary and sufficient conditions for equality over the pseudovariety CR of all finite completely regular semigroups are obtained. They are inspired by the solution of the word problem for free completely regular semigroups and clarify the role played by groups in the structure of such semigroups. A strengthened version of Ash's inevitability theorem (κ-reducibility of the pseudovariety G of all finite groups) is proposed as an open problem and it is shown that, if this stronger version holds, then CR is also κ-reducible and, therefore, hyperdecidable.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 63 , Issue 3 , June 2001 , pp. 407 - 433
Copyright
Copyright © Australian Mathematical Society 2001

References

[1]Almeida, J., Finite semigroups and universal algebra, Series in Algebra 3, (English translation) (World Scientific, Singapore, 1995).Google Scholar
[2]Almeida, J., ‘A syntactical proof of locality of DA’, Internat. J. Algebra Comput. 6 (1996), 165–177.CrossRefGoogle Scholar
[3]Almeida, J., ‘Hyperdecidable pseudovarieties and the calculation of semidirect products’, Internat. J. Algebra Comput. 9 (1999), 241–261.CrossRefGoogle Scholar
[4]Almeida, J., Azevedo, A., and Teixeira, L., ‘On finitely based pseudovarieties of the forms V ∗ D and V ∗ Dn’, J. Pure Appl. Algebra 146 (2000), 1–15.CrossRefGoogle Scholar
[5]Almeida, J. and Delgado, M., ‘Sur certains systèmes d'équations avec contraintes dans un groupe libre’, Portugal. Math. 56 (1999), 409–417.Google Scholar
[6]Almeida, J. and Delgado, M., ‘Sur certains systèmes d'équations avec contraintes dans un groupe libre—addenda’, (Technical Report CMUP 1999–22) Univ. Porto, (1999).Google Scholar
[7]Almeida, J. and Steinberg, B., ‘On the decidability of iterated semidirect products and applications to complexity’, Proc. London Math. Soc. 80 (2000), 50–74.CrossRefGoogle Scholar
[8]Almeida, J. and Steinberg, B., ‘Syntactic and global semigruop theory, a synthesis approach’, in Algorithmic Problems in Groups and Semigroups, (Birget, J. C., Margolis, S. W., and Sapir, M. V., Editors), Trends Math. (Birkhäuser Boston, Boston, MA, 2000).Google Scholar
[9]Almeida, J. and Trotter, P. G., ‘Hyperdecidability of pseudovarieties of orthogroups’, Glasgow Math. J. (to appear).Google Scholar
[10]Almeida, J. and Weil, P., ‘Relatively free profinite monoids: an introduction and examples’, in Semigroups, Formal Languages and Groups 466, (Fountain, J. B., Editor) (Kluwer Academic Publ., Dordrecht, 1995), pp. 73–117.CrossRefGoogle Scholar
[11]Almeida, J. and Weil, P., ‘Profinite categories and semidirect products’, J. Pure Appl. Algebra 123 (1998), 1–50.CrossRefGoogle Scholar
[12]Ash, C.J., ‘Inevitable graphs: a proof of the type II conjecture and some related decision procedures’, Internat. J. Algebra Comput. 1 (1991), 127–146.CrossRefGoogle Scholar
[13]Eilenberg, S., Automata, Languages and Machines, Vol. B (Academic Press, New York, 1976).Google Scholar
[14]Kaďourek, J. and Polák, L., ‘On the word problem for free completely regular semigroups’, Semigroup Forum 34 (1986), 127–138.CrossRefGoogle Scholar
[15]Pastijn, F.J. and Trotter, P.G., ‘Residual finiteness in completely regular semigroup varieties’, Semigroup Forum 37 (1988), 127–147.CrossRefGoogle Scholar
[16]Reilly, N.R., ‘The Rhodes expansion and free objects in varieties of completely regular semigroups’, J. Pure Appl. Algebra 69 (1990), 89–109.CrossRefGoogle Scholar
[17]Rhodes, J., ‘Undecidability, automata and pseudovarieties of finite semigroups’, Internat. J. Algebra Comput. 9 (1999), 455–473.Google Scholar
[18]Steinberg, B. ‘Finite state automata: a geometric approach’ Trans. Amer, Math. Soc. (to appear).Google Scholar
[19]Trotter, P.G., ‘Free completely regular semigroups’, Glasgow Math. J. 25 (1984), 241–254.CrossRefGoogle Scholar