home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / prolog / 2289 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  2.5 KB
  1. Xref: sparky comp.lang.prolog:2289 comp.theory:2745
  2. Path: sparky!uunet!destroyer!ncar!noao!arizona!naiwei
  3. From: naiwei@cs.arizona.edu (Nai-Wei Lin)
  4. Newsgroups: comp.lang.prolog,comp.theory
  5. Subject: CASLOG is available
  6. Keywords: Automatic Complexity Analysis, Logic Programs
  7. Message-ID: <28709@optima.cs.arizona.edu>
  8. Date: 21 Dec 92 22:01:21 GMT
  9. Followup-To: poster
  10. Organization: U of Arizona CS Dept, Tucson
  11. Lines: 47
  12.  
  13.  
  14.     CASLOG - A Complexity Analysis System for Logic Programs
  15.  
  16. The CASLOG system is now available. 
  17.  
  18. CASLOG (Complexity Analysis System for LOGic) is an experimental 
  19. semi-automatic complexity analysis system for logic programs. 
  20. It can perform the worst-case analysis for complexity measures: 
  21. argument size complexity, number of solutions complexity, and 
  22. time complexity.
  23.  
  24. CASLOG extends the techniques developed for analyzing imperative and 
  25. functional languages to deal with nondeterminism and generation of 
  26. multiple solutions via backtracking in logic languages. The analyses
  27. for different complexity measures are implemented in a unified framework
  28. and share several common features. First, the predicates in a program
  29. are processed in a order generated by a bottom-up topological sorting 
  30. over the call graph of the program. Second, the complexity function for
  31. a predicate is derived from the complexity function of its clauses by
  32. using the information about the mutual exclusion relationships between
  33. its clauses. Third, the complexity function for a clause is inferred
  34. based on the data dependency relationships between its literals. Fourth,
  35. the complexity functions for recursive clauses are in the form of
  36. difference equations and are transformed into closed form functions using
  37. difference equation solving techniques. This unified framework can 
  38. simplify proofs of correctness and the implementation of the algorithms.
  39.  
  40. This unified framework is further enhanced by incorporating the ability of
  41. using graph-theoretic methods to analyze the number of solutions complexity
  42. for predicates that consist of constraints over finite domains. 
  43. Given domain information, the system can handle predicates involving
  44. linear arithmetic constraints and binary disequality constraints.
  45.  
  46. This release is an alpha release. It contains the CASLOG version 1.0,
  47. a preliminary user manual, a paper on CASLOG, and a set of examples.
  48. The system is available by anonymous ftp from
  49.  
  50. cs.arizona.edu
  51.  
  52. in the directory caslog.
  53.  
  54. Nai-Wei Lin                     
  55. Department of Computer Science
  56. The University of Arizona
  57. Tucson, Arizona 85721
  58. USA
  59. naiwei@cs.arizona.edu
  60.