CMU Artificial Intelligence Repository
Home INFO Search FAQs Repository Root

CASLOG: Complexity Analysis System for LOGic

CASLOG (Complexity Analysis System for LOGic) is an experimental semi-automatic complexity analysis system for logic programs. It can perform the worst-case analysis for complexity measures: argument size complexity, number of solutions complexity, and time complexity. CASLOG extends the techniques developed for analyzing imperative and functional languages to deal with nondeterminism and generation of multiple solutions via backtracking in logic languages. The analyses for different complexity measures are implemented in a unified framework and share several common features. First, the predicates in a program are processed in an order generated by a bottom-up topological sorting over the call graph of the program. Second, the complexity function for a predicate is derived from the complexity function of its clauses by using the information about the mutual exclusion relationships between its clauses. Third, the complexity function for a clause is inferred based on the data dependency relationships between its literals. Fourth, the complexity functions for recursive clauses are in the form of difference equations and are transformed into closed form functions using difference equation solving techniques. This unified framework can simplify proofs of correctness and the implementation of the algorithms.

Version: 1.0 alpha (20-DEC-92) Requires: SICStus Prolog and C CD-ROM: Prime Time Freeware for AI, Issue 1-1 Author(s): Nai-Wei Lin Department of Computer Science University of Arizona Keywords: Authors!Lin, Benchmarks!Prolog, CASLOG, Complexity Analysis, Prolog!Benchmarks, Prolog!Code, Prolog!Tools References: The distribution includes a user manual, a paper on CASLOG, and a set of benchmark examples.
Last Web update on Mon Feb 13 10:34:03 1995