home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 16981 < prev    next >
Encoding:
Internet Message Format  |  1992-12-15  |  3.9 KB
  1. Path: sparky!uunet!mcsun!uknet!qmw-dcs!arodgers
  2. From: arodgers@dcs.qmw.ac.uk (Angus H Rodgers)
  3. Newsgroups: sci.math
  4. Subject: Re: A word problem
  5. Message-ID: <1992Dec15.221213.6274@dcs.qmw.ac.uk>
  6. Date: 15 Dec 92 22:12:13 GMT
  7. References: <1992Dec12.162349.29729@dcs.qmw.ac.uk> <djoyce.724444576@black.clarku.edu>
  8. Sender: usenet@dcs.qmw.ac.uk (Usenet News System)
  9. Organization: Computer Science Dept, QMW, University of London
  10. Lines: 72
  11. Nntp-Posting-Host: theoryc.dcs.qmw.ac.uk
  12.  
  13. In <djoyce.724444576@black.clarku.edu>
  14. djoyce@black.clarku.edu (Dave Joyce) writes:
  15.  
  16. >In <1992Dec12.162349.29729@dcs.qmw.ac.uk>
  17. >arodgers@dcs.qmw.ac.uk (Angus H Rodgers) writes:
  18.  
  19. >>Are there any finitely generated infinite semigroups in which
  20. >>the idempotent law holds?
  21. >>
  22. >>The "free idempotent semigroup" (if that's the name for it) on
  23. >>2 generators has 6 elements. I don't know if the f.i.s. on 3
  24. >>generators is infinite, but it's certainly quite big.
  25. >>
  26. >[Description and comments for problem with an alphabet {a,b,c} deleted]
  27. >>
  28. >>Is there, nevertheless, a recipe or existence proof for arbitarily
  29. >>long reduced words?
  30.  
  31. >This is a very interesting problem, but I haven't made any progress on it yet.
  32. >[....]
  33. >Sometimes the source of a problem helps in solving the problem.  I'd like to
  34. >know more about it.
  35.  
  36. I had some amazingly prompt responses to my article, on the day it was
  37. posted, at the weekend. My thanks go especially to Mark "V." Sapir and
  38. Nicholas Reingold, whose virtually instantaneous and simultaneous replies
  39. supplied all the information I needed, and convinced me that sci.math
  40. has some previously unsuspected oracular qualities. I'll summarise the
  41. replies when I have time (probably after Christmas ...). Meanwhile, I'll 
  42. just say that the answer to my question is known, and can be found in:
  43.  
  44.     Lallement, Gerard
  45.        Semigroups and combinatorial applications / [by] Gerard Lallement.
  46.        New York : Wiley, 1979. - xiii,376p : ill ; 24cm. - (Pure and
  47.        applied mathematics)
  48.        'A Wiley-Interscience publication'. - Text on lining paper. - Bibl.:
  49.        p.357-368. - Index. - 0-471-04379-6
  50.  
  51. (At least, I'm told it can; but a computer error has prevented me from
  52. borrowing the book and making sure. Aargh! I hate computers!)
  53.  
  54. I had also better admit, with some embarrassment, that my presentation
  55. of the problem was confused, in that I used the term "reduced words" to
  56. refer to strings over the alphabet {a,b,c} which are (in the correct
  57. terminology) "squarefree", i.e. have no nonempty substrings of the form 
  58. xx; *but* distinct squarefree strings may nevertheless denote equal elements
  59. in all idempotent semigroups -- because the reduction rule xx = x can be 
  60. applied in both directions. (It never even entered my head that the
  61. backwards application could be needed.) There are, indeed, recipes for
  62. constructing infinite squarefree strings over a 3-character alphabet, but
  63. it does not follow from this that infinite 3-generated idempotent
  64. semigroups exist, and I'm sorry that I gave the misleading impression that
  65. there was such an implication.
  66.  
  67. >Does anyone know examples of idempotent semigroups (or idempotent monoids)
  68. >besides the commutative ones?  (Commutative ones are semilattices and don't
  69. >help with this problem.)
  70.  
  71. When I dallied with this problem last year (somebody mentioned 
  72. semilattices, and somebody else wondered what would happen if you
  73. dropped the commutativity condition, but none of us had worked in
  74. this area), I thought of some examples, and I think I reduced them all
  75. to this one construction (which, I now learn, is called a "rectangular
  76. band"): take any two sets A, B (nonempty, and not both singletons, if
  77. you want to avoid commutativity), and on the Cartesian product AxB
  78. define an associative, idempotent binary operation * by putting
  79. (a,b) * (a',b') := (a,b').
  80. --
  81. Gus Rodgers,  Dept. of Computer Science, | 
  82. Queen Mary & Westfield College, Mile End | 
  83. Road, London, England.   +44 71 975 5241 | 
  84. E-mail (JANET):   arodgers@dcs.qmw.ac.uk | Post in haste, repent at leisure.
  85.