Input Format

We use an adapted version of the format for Integer Programs (IPs, see for example here or here) from the Termination and Complexity Competition extended by costs. Furthermore, we introduce IPs with function calls (ϱ-IPs) and also probabilistic IPs (PIPs).

Integer Programs (IPs)

(GOAL COMPLEXITY)
(STARTTERM (FUNCTIONSYMBOLS f))
(VAR x y)
(RULES
  f(x,y) -{0}> g(x,y)
  g(x,y) -> g(x-1,y+x) :|: x > 0
  g(x,y) -> h(x,y)
  h(x,y) -{y}> h(x,y-1) :|: y > 0
)

• The first line (GOAL COMPLEXITY) indicates that we would like to compute upper bounds on the runtime of the given IP.
• The second line (STARTTERM (FUNCTIONSYMBOLS f)) specifies that f is the start location of the IP.
• The third line (VAR x y) specifies that the program variables used in the system are x and y. The program may use additional temporary variables.
• The fourth line (RULES ... indicates that we now state the general transitions of our system. It is ended by a closing parenthesis ) in the last line of the example code above.
• The remaining lines contain the transitions of the program in the form LHS -{COST}> RHS (:|: GUARD) or LHS -> RHS (:|: GUARD).
  • LHS is the start location of the transition including the variables to be updated here, e.g., f(x,y). Locations are arbitrary alpha-numerical strings.
  • COST is a non-negative polynomial that bounds the cost of the transition. This is optional. If omitted, the cost defaults to 1.
  • RHS specifies the guard and the update of a transition.
    • Updates are polynomial expressions. If the updates contain variables which are not given on the left-hand side, they are treated as non-deterministic (those variables can be restricted in the guard).
      • For example, g(x,y) -> g(x-1,y+x) means that from the start location g, x is set to x-1 and y is set to y+x.
      • For example, g(x,y) -> g(z,y) means that from the start location g, the IP chooses the transition to location g where the first variable x is updated non-deterministically and the second variable y stays the same.
  • GUARD is a conjunction (using the connective &&) of linear (in)equalities representing the guard of the transition, e.g., x > 0 or x > 0 && 2 * x + 3 * y = 0. This is optional. If omitted, GUARD defaults to true, e.g., g(x,y) -{0}> h(x,y).

Integer Programs with Function Calls (ϱ-IPs)

In addition to IPs, we also allow function calls and so-called return locations. See our article here for the formal semantics.

(GOAL COMPLEXITY)
(STARTTERM (FUNCTIONSYMBOLS l0))
(RETURNLOCATIONS (FUNCTIONSYMBOLS f2))
(VAR x y a)
(RULES
  # Computes the sum x! + ... + 1! at l1
  # and afterwards uses this result in the second loop at l2.
  l0(x,y,a) -> l1(x,y,a)
  l1(x,y,a) -> l1(x-1,y+f1[a | (x,y,a) <- (x,y,x)],a) :|: x > 0
  l1(x,y,a) -> l2(1,y,a) :|: x <= 0
  l2(x,y,a) -> l2(2*x,3*y,a) :|: x < y

  # Recursively computes the factorial a!.
  f1(x,y,a) -> f2(x,y,1) :|: a = 0
  f1(x,y,a) -> f2(x,y,a*f1[a | (x,y,a) <- (x,y,a - 1)]) :|: a > 0
)

Here, a function call has the form l[ v | L <- R ] where L is a tuple of variables and R is a tuple of polynomial expressions. Here, l is the start location of the subprogram that is called, the update L <- R sets the program variables of the subprogram to their initial values, and v contains the “return value” of the subprogram upon its termination. In the example, we have two function calls f1[a | (x,y,a) <- (x,y,x)] and f1[a | (x,y,a) <- (x,y,a - 1)]. Furthermore, the return locations are specified in the third line (RETURNLOCATIONS (FUNCTIONSYMBOLS ...)).

Probabilistic Integer Programs (PIPs)

(GOAL EXPECTEDCOMPLEXITY)
(STARTTERM (FUNCTIONSYMBOLS f))
(VAR x y)
(RULES
  f(x,y) -{0}> g(x,y)
  g(x,y) -> 0.5:g(x-1,y+x) :+: 0.5:g(x,y+x) :|: x > 0
  g(x,y) -{0}> h(x,y)
  h(x,y) -> h(x,y-1) :|: y > 0
)

• The first line (GOAL EXPECTEDCOMPLEXITY) indicates that we would like to compute upper bounds on the expected runtime of the given PIP. Alternatively, (GOAL COMPLEXITY) can be used to analyse an over-approximation, i.e., replacing all probabilities by non-deterministic choices, of the PIP.
• In contrast to IPs, the remaining lines contain the general transitions of the program in the form LHS -{COST}> RHS (:|: GUARD) or LHS -> RHS (:|: GUARD).
  • LHS again is the start location of the general transition.
  • Here, COST is a non-negative integer constant that bounds the cost of the general transition.
  • RHS specifies the distribution over transitions in the general transition.
    • Elements of the transition are given by p:target(up1,...,upn) and are separated by :+:. This means that the variable x1 is updated to up1,…,upn the variable xn is updated to upn, and the system transitions to location target with probability p.
    • Probabilities are rational numbers strictly greater than 0 which must add up to 1.
    • In case of a singleton general transition, the probability can be omitted and then defaults to 1, e.g., f(x,y) -{0}> g(x,y).
    • Updates are polynomial expressions. If the updates contain variables which are not given on the left-hand side, they are treated as non-deterministic (those variables can be restricted in the guard).
      • For example, g(x,y) -> 0.5:g(x-1,y+x) :+: 0.5:g(x,y+x) means that from the start location g, with probability 0.5 x is set to x-1 and y is set to y+x, and with the remaining probability 0.5 x is set to x and y is set to y+x.
      • For example, g(x,y) -> 1:g(z,y) means that from the start location g, the PIP chooses the transition to location g where the first variable x is updated non-deterministically and the second variable y stays the same.
    • Updates can also be distribution functions. For example, g(x,y) -> g(x,y + GEOMETRIC(0.5)) means that in the transition from the location g, the variable x stays the same whereas y is increased by a value drawn from a geometric distribution with parameter 0.5.
      • At the moment, we support the following discrete distributions. Here, parameters are integer polynomial expressions, i.e., they may depend on variables, whereas constants are non-negative integers or non-negative rationals. The user has to ensure that their values meet the stated constraints:
        • Bernoulli distribution with rational constant 0 < p < 1 via BERNOULLI(p).
        • Binomial distribution with rational constant 0 < p < 1 and a non-negative integer parameter n via BINOMIAL(n,p).
        • Geometric distribution with rational constant 0 < p < 1 via GEOMETRIC(p).
        • Hypergeometric distribution with non-negative integer constant N and non-negative integer parameters k,n via HYPERGEOMETRIC(N,k,n).
        • Uniform distribution with integer parameters a <= b via UNIFORM(a,b).