Data Structure for Complexity Models

October 20, 2021

Import statement from "ri.newgen"

(Avoids conflicts between number types and types defined by the RI)

External Ppolynome

The domain Ppolynome is used to represent the complexities of the statement as function of parameters, variables and indices of loops with lobal coverage. A Ppolynome is a list of monomials, each monomial being constited of a floating coefficient and a Pvecteur representing the product of variables with their expopents.

Complexity = eval:Ppolynome x varcount x rangecount x ifcount

In the course of the evaluation, a field complexity is associated with each statement. The sub-domain eval contains a polynome Approching the complexity of the statement. The sub-domains varcount, rangecount and ifcount give the information statistics concerning the mnner in which the evaluation of the complexity took place, therefore also of the complexity itself. They count and in so doing classify the different types of variables/loops/tests encountered in the course of the complexity’s evaluation.

Varcount = symbolic:int x guessed:int x bounded:int x unknown:int

Rangecount = profiled:int x guessed:int x bounded:int x unknown:int

Ifcount = profiled:int x computed:int x halfhalf:int