home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 16769 < prev    next >
Encoding:
Internet Message Format  |  1992-12-12  |  1.4 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: A word problem
  5. Message-ID: <1992Dec12.162349.29729@dcs.qmw.ac.uk>
  6. Date: 12 Dec 92 16:23:49 GMT
  7. Sender: usenet@dcs.qmw.ac.uk (Usenet News System)
  8. Organization: Computer Science Dept, QMW, University of London
  9. Lines: 25
  10. Nntp-Posting-Host: io.dcs.qmw.ac.uk
  11.  
  12. Are there any finitely generated infinite semigroups in which
  13. the idempotent law holds?
  14.  
  15. The "free idempotent semigroup" (if that's the name for it) on
  16. 2 generators has 6 elements. I don't know if the f.i.s. on 3
  17. generators is infinite, but it's certainly quite big.
  18.  
  19. In trying to prove the infiniteness of the f.i.s. over a given
  20. alphabet, say {a,b,c}, you can't build arbitrarily long reduced 
  21. words by a haphazard process of pre- or post- multiplication by 
  22. generators, because some reduced words do not occur as substrings
  23. of any longer ones, e.g.:
  24.  
  25.                               abacaba
  26.                           abacbabcabacbab
  27.                        abcbabcabacabcbabcaba
  28.                   abcbacabcbabcacbabcbacabcbabcac
  29.  
  30. Is there, nevertheless, a recipe or existence proof for arbitarily
  31. long reduced words?
  32. --
  33. Gus Rodgers,  Dept. of Computer Science, | 
  34. Queen Mary & Westfield College, Mile End | 
  35. Road, London, England.   +44 71 975 5241 | 
  36. E-mail (JANET):   arodgers@dcs.qmw.ac.uk | Post in haste, repent at leisure.
  37.