adapt complexity model for complexity competition 2015

[alpako]

I adapted the output to fit the new complexity model ( see http://cl-informatik.uibk.ac.at/users/georg/cbr/competition/rules.php ). Please check whether the changes are correct and if the parsing and printing works as intended.

[jwaldmann]

treating MAYBE as (Infinite,Infinite) is wrong, because an Infinite lower bound would mean non-termination.

[alpako]

OK, I wanted to keep the changes simple. I suggest to introduce complexity hierarchies for upper and lower bounds:

data LowerBound 
  = LBPoly Int
  | LBNonPoly
  | LBUnknown

data UpperBound 
  = UBPoly (Maybe Int)
  | UBUnknown

Then the meaning of the results would be like this:

data Bounds = Bounds LowerBound UpperBound

Bounds LBUnknown    UBUnknown           -- MAYBE
Bounds LBUnknown    (UBPoly Nothing)    -- POLY upperbound
Bounds LBUnknown    (UBPoly (Just nat)) -- O(n^nat) upperbound
Bounds LBUnknown    (UBPoly (Just 0))   -- O(1) upperbound
Bounds LBNonPoly    UBUnknown           -- NON_POLY lowerbound
Bounds (LBPoly nat) UBUnknown           -- Omega(n^nat) lowerbound
Bounds (LBPoly 0)   UBUnknown           -- trivial O(1) lowerbound -> MAYBE

[jwaldmann]

Yes, I'm all for using a proper internal model.

Still, we should keep the current external representation for the moment (to avoid changes that influence this year's competition).

Note that "non-poly" is a very bad idea, see remark at end of http://lists.lri.fr/pipermail/termtools/2015-July/001002.html

If the intention is "exponential", then we should say so.

And while we're at it, we might add a base to the exponential, as 2^n is different from 3^n. Of course we can also have "exponential with unknown base".

[alpako]

The current representation of complexity is

data Function = Poly { degree :: Maybe Int }
              | Finite
              | Infinite

data Bounds = Bounds { lower :: Function
                     , upper :: Function
                     }

Is it a good idea to map the competition's complexity model to the representation like this?

Bounds { lower = Infinite, upper = Infinite }             -- unused
Bounds { lower = Poly $ Just 0, upper = Infinite }        -- MAYBE
Bounds { lower = Poly $ Just nat, upper = Infinite }      -- Omega(n^nat) lower bound with nat > 0
Bounds { lower = Poly Nothing, upper = _ }                -- unused
Bounds { lower = Finite, upper = Infinite }               -- NON_POLY lower bound
Bounds { lower = Poly $ Just 0, upper = Poly $ Just 0 }   -- O(1) upperbound
Bounds { lower = Poly $ Just 0, upper = Poly $ Just nat } -- O(n^nat) upperbound
Bounds { lower = Poly $ Just 0, upper = Poly Nothing }    -- POLY upperbound
Bounds { lower = _ , upper = Finite }                     -- unused

The lower bound of Poly $ Just 0 is equivalent to ?. Upper bound Infinite is equivalent to ?.