home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1905 < prev    next >
Encoding:
Text File  |  1992-09-10  |  1.0 KB  |  26 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!proclus.csd.uwm.edu!litow
  3. From: litow@csd4.csd.uwm.edu (bruce e litow)
  4. Subject: Infinitary codes
  5. Message-ID: <1992Sep10.121359.210@uwm.edu>
  6. Summary: being a `code' w.r.t. omega-strings
  7. Originator: litow@proclus.csd.uwm.edu
  8. Keywords: infinitary codes, omega words
  9. Sender: news@uwm.edu (USENET News System)
  10. Organization: Computing Services Division, University of Wisconsin - Milwaukee
  11. Date: Thu, 10 Sep 1992 12:13:59 GMT
  12. Lines: 12
  13.  
  14. Litovsky mentions work of Staiger concerning sets of words, R, whose omega
  15. power consists of omega words, each with a unique factorization over R.
  16. It is clear for regular R that this property of being an infinitary code
  17. is decidable. Just express the condition in S1S. But in this case,
  18. especially for finite R, is a better decision method known? One with
  19. an interesting complexity upper bound?
  20.  
  21. Bruce Litow
  22. Computing Services Division
  23. P.O. Box 413
  24. Univ. Wisconsin-Milwaukee, Milwaukee, WI, 53201
  25. litow@proclus.csd.uwm.edu
  26.