Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-02-09T03:12:03.597Z Has data issue: false hasContentIssue false
  • English
  • Français

A topological approach to a conjecture of Rhodes

Published online by Cambridge University Press:  17 April 2009

J.E. Pin
J.E. Pin
Affiliation:
L.I.T.P., Tour 55–65, Université Paris VI, 75252 Paris, Cedex 05, France
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.

The “type II conjecture”, proposed by J. Rhodes, gives an algorithm to compute the kernel of a given finite semigroup. We show that this conjecture is a consequence of another conjecture, of a topological nature. This new conjecture gives a simple and effective characterisation of the recognisable subsets of a free monoid that are closed in the finite group topology for the free monoid.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 38 , Issue 3 , December 1988 , pp. 421 - 431
Copyright
Copyright © Australian Mathematical Society 1988

References

[1]Ash, C.J., ‘Finite semigroups with commuting idempotents’, J. Austral. Math. Soc. (Series A) 43 (1987), 81–90.CrossRefGoogle Scholar
[2]Birget, J.C., Margolic, S.W. and Rhodes, J., ‘Finite semigroups whose idempotents commute or form a subsemigroup’, in Semigroups and Their Applications, edited by Goberstein, S.M. and Higgins, P.M. (Reidel, Dordrecht, 1987). pp. 25–35.CrossRefGoogle Scholar
[3]Birget, J.C., Margolic, S.W. and Rhodes, J., ‘Finite semigroups whose idempotents form a semilattice or a band’ (to appear).Google Scholar
[4]Eilenberg, S., Automata, Languages and Machines (Academic Press, New York, Vol A. 1974; Vol. B 1976).Google Scholar
[5]Hall, M. Jr, ‘A topology for free groups and related groups’, Ann. of Maths. 52 (1950), 127–139.CrossRefGoogle Scholar
[6]Lallement, G., Semigroups and Combinatorial Applications (Wiley, New York, 1979).Google Scholar
[7]Margolic, S.W. and Pin, J.E., ‘Varieties of finite monoids and topology for the free monoid’, in Proceedings of the Marquette Semigroup Conference, 1984. pp. 113–130.Google Scholar
[8]Pin, J.E., ‘Finite group topology and p-adic topology for free monoids’, in 12th ICALP, Lecture Notes in Computer Science 199 (Springer, Berlin, 1985). pp. 285–299.Google Scholar
[9]Pin, J.E., Varieties of formal languages (North Oxford Academic, London and Plenum, New York, 1986).CrossRefGoogle Scholar
[10]Pin, J.E., ‘On the languages recognized by finite reversible automat’, in 14th ICALP, Lecture Notes in Computer Science 267 (Springer, Berlin, 1987). pp. 237–249.Google Scholar
[11]Pin, J.E., ‘On a conjecture of Rhodes’, (survey paper), (toappear).Google Scholar
[12]Pin, J.E., ‘Topologies for the free monoid’ (to appear).Google Scholar
[13]Reutenauer, Ch., ‘Une topologie du monoïde libre’, Semigroup Forum 18 (1979), 33–49.CrossRefGoogle Scholar
[14]Reutenauer, Ch., ‘Une topologie du monoïde libe’, Sur mon article, Semigroup Forum 22 (1981), 93–95.CrossRefGoogle Scholar
[15]Rhodes, J., ‘New techniques in global semigroup theory’, in Semigroups and Their Applications, edited by Goberstein, S.M. and Higgins, P.M. (Reidel, Dordrecht, 1987). pp. 169–181.CrossRefGoogle Scholar
[16]Tilson, B. and Rhodes, J., ‘Improved lower bounds for the complexity of finite semigroups’, J. Pure Appl. Algebra 2 (1972), 13–71.Google Scholar
[17]Tilson, B., Chapters 11 and 12 of [4].Google Scholar
[18]Tilson, B., ‘Type II redux’, in Semigroups and Their Applications, edited by Goberstein, S.M. and Higgine, P.M. (Reidel, Dordrecht, 1987). pp. 201–205.CrossRefGoogle Scholar