C Complexity

From Termination-Portal.org
Jump to navigationJump to search

We consider the C-fragment from the category Termination of C Programs, but in contrast to the termination category, the starting point should be stated explicitly. If the program consists of one function only, then the starting point can be omitted.

The notion of complexity is:

#loop iterations + #execution of gotos + #function invocations

In this way, we do not have to deal with too many low-level details (like C vs. LLVM).

The size measure for the arguments is part of the input. However, integers are measured by their absolute value, unless specified otherwise.

Currently, all benchmarks consists of a single function with integer arguments only. We will fix a formalism for specifying the starting point and size measures as soon as somebody wants to submit more complex benchmarks.