PROBABILISTIC COST ANALYSIS OF LOGIC PROGRAMS

cost analyses of logic programs have been developed which make it possible to obtain automatically lower and upper bounds of runtime cost of computations. this information is very useful for a variety of purposes, including granularity control, query optimization in databases, and program transformation and synthesis. however, current techniques suffer a loss of accuracy in some cases which are quite representative (i.e., some divide-and-conquer programs as quicksort). this paper describes an alternative probabilistic approach which makes it possible to figure out an estimate of the execution cost. one of its advantages is that it needs only a few changes over previously proposed schemes.