home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1868 < prev    next >
Encoding:
Text File  |  1992-09-04  |  1002 b   |  27 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!sun-barr!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watdragon.uwaterloo.ca!maytag.uwaterloo.ca!jfbuss
  3. From: jfbuss@maytag.uwaterloo.ca (Jonathan Buss)
  4. Subject: Re: Constructive proof of directed graph unconectivity
  5. Message-ID: <Bu26LJ.BuI@watdragon.uwaterloo.ca>
  6. Keywords: CON NLOG NLOG-Complete
  7. Sender: news@watdragon.uwaterloo.ca (USENET News System)
  8. Organization: University of Waterloo
  9. References: <1992Sep3.161109.22586@sbil.co.uk>
  10. Date: Fri, 4 Sep 1992 14:51:19 GMT
  11. Lines: 14
  12.  
  13. In article <1992Sep3.161109.22586@sbil.co.uk> tdk@spitws75.sbil.co.uk writes:
  14. >Immerman and Szelepcsenyi have shown NLOG = CO-NLOG so combining these
  15. >results we see UNCON is indeed in NLOG.
  16. >
  17. >Is there a direct constructive proof of this fact ?
  18.  
  19. Yes.  Both Immerman and Szelepcsenyi proved the result by direct
  20. construction.  An alternative formulation is given by Balcazar, Diaz
  21. and Gabarro in _Structural_Complexity_II_, Springer-Verlag, 1990.
  22.  
  23. >Tim Kempster
  24.  
  25. Jonathan Buss
  26.  
  27.