🚀 go-pugleaf

	CASLOG - A Complexity Analysis System for Logic Programs

The CASLOG system is now available. 

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 a 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.

This unified framework is further enhanced by incorporating the ability of
using graph-theoretic methods to analyze the number of solutions complexity
for predicates that consist of constraints over finite domains. 
Given domain information, the system can handle predicates involving
linear arithmetic constraints and binary disequality constraints.

This release is an alpha release. It contains the CASLOG version 1.0,
a preliminary user manual, a paper on CASLOG, and a set of examples.
The system is available by anonymous ftp from

cs.arizona.edu

in the directory caslog.

Nai-Wei Lin					 
Department of Computer Science
The University of Arizona
Tucson, Arizona 85721
USA
naiwei@cs.arizona.edu