### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f 0: f -> fib : [], cost: 0 1: fib -> fib : x'=-1+x, fib : x'=-2+x, [ x>1 ], cost: 1 2: fib -> sink : [ x<=1 ], cost: 1 Checking for constant complexity: Could not prove constant complexity. Removed unreachable and leaf rules: Start location: f 0: f -> fib : [], cost: 0 1: fib -> fib : x'=-1+x, fib : x'=-2+x, [ x>1 ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: fib -> fib : x'=-1+x, fib : x'=-2+x, [ x>1 ], cost: 1 Accelerated rule 1 with metering function meter (where 2*meter==-1+x), yielding the new rule 3. Removing the simple loops: 1. Accelerated all simple loops using metering functions (where possible): Start location: f 0: f -> fib : [], cost: 0 3: fib -> [3] : [ x>1 && 2*meter==-1+x ], cost: -1+2^meter Chained accelerated rules (with incoming rules): Start location: f 0: f -> fib : [], cost: 0 4: f -> [3] : [ x>1 && 2*meter==-1+x ], cost: -1+2^meter Removed unreachable locations (and leaf rules with constant cost): Start location: f 4: f -> [3] : [ x>1 && 2*meter==-1+x ], cost: -1+2^meter ### Obtained a tail recursive problem, continuing simplification ### ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f 4: f -> [3] : [ x>1 && 2*meter==-1+x ], cost: -1+2^meter Computing asymptotic complexity for rule 4 Solved the limit problem by the following transformations: Created initial limit problem: -1+x (+/+!), -1+2^meter (+), -2*meter+x (+/+!), 2+2*meter-x (+/+!) [not solved] applying transformation rule (C) using substitution {x==1+2*meter} resulting limit problem: 1 (+/+!), -1+2^meter (+), 2*meter (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: -1+2^meter (+), 2*meter (+/+!) [not solved] applying transformation rule (E), replacing -1+2^meter (+) by 1 (+/+!) and meter (+) resulting limit problem: 1 (+/+!), meter (+), 2*meter (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: meter (+), 2*meter (+/+!) [not solved] applying transformation rule (A), replacing 2*meter (+) by meter (+) and 2 (+!) using + limit vector (+,+!) resulting limit problem: meter (+), 2 (+!) [not solved] applying transformation rule (B), deleting 2 (+!) resulting limit problem: meter (+) [solved] Solved the limit problem by the following transformations: Created initial limit problem: -1+x (+/+!), -1+2^meter (+), -2*meter+x (+/+!), 2+2*meter-x (+/+!) [not solved] applying transformation rule (C) using substitution {x==1+2*meter} resulting limit problem: 1 (+/+!), -1+2^meter (+), 2*meter (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: -1+2^meter (+), 2*meter (+/+!) [not solved] applying transformation rule (E), replacing -1+2^meter (+) by 1 (+/+!) and meter (+) resulting limit problem: 1 (+/+!), meter (+), 2*meter (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: meter (+), 2*meter (+/+!) [not solved] applying transformation rule (A), replacing 2*meter (+) by meter (+) and 2 (+!) using + limit vector (+,+!) resulting limit problem: meter (+), 2 (+!) [not solved] applying transformation rule (B), deleting 2 (+!) resulting limit problem: meter (+) [solved] Solution: meter / n x / 1+2*n Resulting cost -1+2^n has complexity: Exp Found new complexity Exp. Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Exp Cpx degree: Exp Solved cost: -1+2^n Rule cost: -1+2^meter Rule guard: [ x>1 && 2*meter==-1+x ] WORST_CASE(EXP,?)