5.37/2.52 WORST_CASE(Omega(n^1), O(n^1)) 5.37/2.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 5.37/2.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.37/2.53 5.37/2.53 5.37/2.53 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(1, 1 + Arg_0 + -1 * Arg_1) + nat(2 * Arg_2 + -2 * Arg_3) + nat(Arg_0 + -1 * Arg_1)). 5.37/2.53 5.37/2.53 (0) CpxIntTrs 5.37/2.53 (1) Koat2 Proof [FINISHED, 845 ms] 5.37/2.53 (2) BOUNDS(1, max(1, 1 + Arg_0 + -1 * Arg_1) + nat(2 * Arg_2 + -2 * Arg_3) + nat(Arg_0 + -1 * Arg_1)) 5.37/2.53 (3) Loat Proof [FINISHED, 921 ms] 5.37/2.53 (4) BOUNDS(n^1, INF) 5.37/2.53 5.37/2.53 5.37/2.53 ---------------------------------------- 5.37/2.53 5.37/2.53 (0) 5.37/2.53 Obligation: 5.37/2.53 Complexity Int TRS consisting of the following rules: 5.37/2.53 eval(A, B, C, D, E) -> Com_1(eval(A, B + 1, C, D, E + 1)) :|: A >= B + 1 && C >= D + 1 5.37/2.53 eval(A, B, C, D, E) -> Com_1(eval(A, B, C, D + 1, E + 1)) :|: A >= B + 1 && C >= D + 1 5.37/2.53 eval(A, B, C, D, E) -> Com_1(eval(A, B, C, D + 1, E + 1)) :|: B >= A && C >= D + 1 5.37/2.53 eval(A, B, C, D, E) -> Com_1(eval(A, B + 1, C, D, E + 1)) :|: A >= B + 1 && D >= C 5.37/2.53 start(A, B, C, D, E) -> Com_1(eval(A, B, C, D, E)) :|: TRUE 5.37/2.53 5.37/2.53 The start-symbols are:[start_5] 5.37/2.53 5.37/2.53 5.37/2.53 ---------------------------------------- 5.37/2.53 5.37/2.53 (1) Koat2 Proof (FINISHED) 5.37/2.53 YES( ?, 1+max([0, Arg_0-Arg_1])+max([0, Arg_2-Arg_3])+max([0, Arg_2-Arg_3])+max([0, Arg_0-Arg_1]) {O(n)}) 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Initial Complexity Problem: 5.37/2.53 5.37/2.53 Start: start 5.37/2.53 5.37/2.53 Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3, Arg_4 5.37/2.53 5.37/2.53 Temp_Vars: 5.37/2.53 5.37/2.53 Locations: eval, start 5.37/2.53 5.37/2.53 Transitions: 5.37/2.53 5.37/2.53 eval(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> eval(Arg_0,Arg_1+1,Arg_2,Arg_3,Arg_4+1):|:Arg_1+1 <= Arg_0 && Arg_3+1 <= Arg_2 5.37/2.53 5.37/2.53 eval(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> eval(Arg_0,Arg_1,Arg_2,Arg_3+1,Arg_4+1):|:Arg_1+1 <= Arg_0 && Arg_3+1 <= Arg_2 5.37/2.53 5.37/2.53 eval(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> eval(Arg_0,Arg_1,Arg_2,Arg_3+1,Arg_4+1):|:Arg_0 <= Arg_1 && Arg_3+1 <= Arg_2 5.37/2.53 5.37/2.53 eval(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> eval(Arg_0,Arg_1+1,Arg_2,Arg_3,Arg_4+1):|:Arg_1+1 <= Arg_0 && Arg_2 <= Arg_3 5.37/2.53 5.37/2.53 start(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> eval(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|: 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Timebounds: 5.37/2.53 5.37/2.53 Overall timebound: 1+max([0, Arg_0-Arg_1])+max([0, Arg_2-Arg_3])+max([0, Arg_2-Arg_3])+max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval: max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval: max([0, Arg_2-Arg_3]) {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval: max([0, Arg_2-Arg_3]) {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval: max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 4: start->eval: 1 {O(1)} 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Costbounds: 5.37/2.53 5.37/2.53 Overall costbound: 1+max([0, Arg_0-Arg_1])+max([0, Arg_2-Arg_3])+max([0, Arg_2-Arg_3])+max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval: max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval: max([0, Arg_2-Arg_3]) {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval: max([0, Arg_2-Arg_3]) {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval: max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 4: start->eval: 1 {O(1)} 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Sizebounds: 5.37/2.53 5.37/2.53 `Lower: 5.37/2.53 5.37/2.53 0: eval->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval, Arg_1: Arg_1 {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval, Arg_3: Arg_3 {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval, Arg_4: Arg_4 {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_1: Arg_1 {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_3: Arg_3 {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_4: Arg_4 {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_1: Arg_1 {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_3: Arg_3 {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_4: Arg_4 {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_1: Arg_1 {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_3: Arg_3 {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_4: Arg_4 {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_1: Arg_1 {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_3: Arg_3 {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_4: Arg_4 {O(n)} 5.37/2.53 5.37/2.53 `Upper: 5.37/2.53 5.37/2.53 0: eval->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval, Arg_1: Arg_1+max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval, Arg_3: Arg_3+max([0, Arg_2-Arg_3]) {O(n)} 5.37/2.53 5.37/2.53 0: eval->eval, Arg_4: Arg_4+max([0, Arg_2-Arg_3])+max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_1: Arg_1+max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_3: Arg_3+max([0, Arg_2-Arg_3]) {O(n)} 5.37/2.53 5.37/2.53 1: eval->eval, Arg_4: Arg_4+max([0, Arg_2-Arg_3])+max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_1: max([Arg_1, Arg_1+max([0, Arg_0-Arg_1])]) {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_3: max([Arg_3, Arg_3+max([0, Arg_2-Arg_3])])+max([0, Arg_2-Arg_3]) {O(n)} 5.37/2.53 5.37/2.53 2: eval->eval, Arg_4: max([Arg_4, Arg_4+max([0, Arg_2-Arg_3])+max([0, Arg_0-Arg_1])])+max([0, Arg_2-Arg_3]) {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_1: max([Arg_1, Arg_1+max([0, Arg_0-Arg_1])])+max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_3: max([Arg_3, Arg_3+max([0, Arg_2-Arg_3])]) {O(n)} 5.37/2.53 5.37/2.53 3: eval->eval, Arg_4: max([Arg_4, Arg_4+max([0, Arg_2-Arg_3])+max([0, Arg_0-Arg_1])])+max([0, Arg_0-Arg_1]) {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_0: Arg_0 {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_1: Arg_1 {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_2: Arg_2 {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_3: Arg_3 {O(n)} 5.37/2.53 5.37/2.53 4: start->eval, Arg_4: Arg_4 {O(n)} 5.37/2.53 5.37/2.53 5.37/2.53 ---------------------------------------- 5.37/2.53 5.37/2.53 (2) 5.37/2.53 BOUNDS(1, max(1, 1 + Arg_0 + -1 * Arg_1) + nat(2 * Arg_2 + -2 * Arg_3) + nat(Arg_0 + -1 * Arg_1)) 5.37/2.53 5.37/2.53 ---------------------------------------- 5.37/2.53 5.37/2.53 (3) Loat Proof (FINISHED) 5.37/2.53 5.37/2.53 5.37/2.53 ### Pre-processing the ITS problem ### 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Initial linear ITS problem 5.37/2.53 5.37/2.53 Start location: start 5.37/2.53 5.37/2.53 0: eval -> eval : B'=1+B, E'=1+E, [ A>=1+B && C>=1+D ], cost: 1 5.37/2.53 5.37/2.53 1: eval -> eval : D'=1+D, E'=1+E, [ A>=1+B && C>=1+D ], cost: 1 5.37/2.53 5.37/2.53 2: eval -> eval : D'=1+D, E'=1+E, [ B>=A && C>=1+D ], cost: 1 5.37/2.53 5.37/2.53 3: eval -> eval : B'=1+B, E'=1+E, [ A>=1+B && D>=C ], cost: 1 5.37/2.53 5.37/2.53 4: start -> eval : [], cost: 1 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 ### Simplification by acceleration and chaining ### 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Accelerating simple loops of location 0. 5.37/2.53 5.37/2.53 Accelerating the following rules: 5.37/2.53 5.37/2.53 0: eval -> eval : B'=1+B, E'=1+E, [ A>=1+B && C>=1+D ], cost: 1 5.37/2.53 5.37/2.53 1: eval -> eval : D'=1+D, E'=1+E, [ A>=1+B && C>=1+D ], cost: 1 5.37/2.53 5.37/2.53 2: eval -> eval : D'=1+D, E'=1+E, [ B>=A && C>=1+D ], cost: 1 5.37/2.53 5.37/2.53 3: eval -> eval : B'=1+B, E'=1+E, [ A>=1+B && D>=C ], cost: 1 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Accelerated rule 0 with metering function A-B, yielding the new rule 5. 5.37/2.53 5.37/2.53 Accelerated rule 1 with metering function C-D, yielding the new rule 6. 5.37/2.53 5.37/2.53 Accelerated rule 2 with metering function C-D, yielding the new rule 7. 5.37/2.53 5.37/2.53 Accelerated rule 3 with metering function A-B, yielding the new rule 8. 5.37/2.53 5.37/2.53 Removing the simple loops: 0 1 2 3. 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Accelerated all simple loops using metering functions (where possible): 5.37/2.53 5.37/2.53 Start location: start 5.37/2.53 5.37/2.53 5: eval -> eval : B'=A, E'=A+E-B, [ A>=1+B && C>=1+D ], cost: A-B 5.37/2.53 5.37/2.53 6: eval -> eval : D'=C, E'=C-D+E, [ A>=1+B && C>=1+D ], cost: C-D 5.37/2.53 5.37/2.53 7: eval -> eval : D'=C, E'=C-D+E, [ B>=A && C>=1+D ], cost: C-D 5.37/2.53 5.37/2.53 8: eval -> eval : B'=A, E'=A+E-B, [ A>=1+B && D>=C ], cost: A-B 5.37/2.53 5.37/2.53 4: start -> eval : [], cost: 1 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Chained accelerated rules (with incoming rules): 5.37/2.53 5.37/2.53 Start location: start 5.37/2.53 5.37/2.53 4: start -> eval : [], cost: 1 5.37/2.53 5.37/2.53 9: start -> eval : B'=A, E'=A+E-B, [ A>=1+B && C>=1+D ], cost: 1+A-B 5.37/2.53 5.37/2.53 10: start -> eval : D'=C, E'=C-D+E, [ A>=1+B && C>=1+D ], cost: 1+C-D 5.37/2.53 5.37/2.53 11: start -> eval : D'=C, E'=C-D+E, [ B>=A && C>=1+D ], cost: 1+C-D 5.37/2.53 5.37/2.53 12: start -> eval : B'=A, E'=A+E-B, [ A>=1+B && D>=C ], cost: 1+A-B 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Removed unreachable locations (and leaf rules with constant cost): 5.37/2.53 5.37/2.53 Start location: start 5.37/2.53 5.37/2.53 9: start -> eval : B'=A, E'=A+E-B, [ A>=1+B && C>=1+D ], cost: 1+A-B 5.37/2.53 5.37/2.53 10: start -> eval : D'=C, E'=C-D+E, [ A>=1+B && C>=1+D ], cost: 1+C-D 5.37/2.53 5.37/2.53 11: start -> eval : D'=C, E'=C-D+E, [ B>=A && C>=1+D ], cost: 1+C-D 5.37/2.53 5.37/2.53 12: start -> eval : B'=A, E'=A+E-B, [ A>=1+B && D>=C ], cost: 1+A-B 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 ### Computing asymptotic complexity ### 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Fully simplified ITS problem 5.37/2.53 5.37/2.53 Start location: start 5.37/2.53 5.37/2.53 9: start -> eval : B'=A, E'=A+E-B, [ A>=1+B && C>=1+D ], cost: 1+A-B 5.37/2.53 5.37/2.53 10: start -> eval : D'=C, E'=C-D+E, [ A>=1+B && C>=1+D ], cost: 1+C-D 5.37/2.53 5.37/2.53 11: start -> eval : D'=C, E'=C-D+E, [ B>=A && C>=1+D ], cost: 1+C-D 5.37/2.53 5.37/2.53 12: start -> eval : B'=A, E'=A+E-B, [ A>=1+B && D>=C ], cost: 1+A-B 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Computing asymptotic complexity for rule 9 5.37/2.53 5.37/2.53 Solved the limit problem by the following transformations: 5.37/2.53 5.37/2.53 Created initial limit problem: 5.37/2.53 5.37/2.53 C-D (+/+!), 1+A-B (+), A-B (+/+!) [not solved] 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 removing all constraints (solved by SMT) 5.37/2.53 5.37/2.53 resulting limit problem: [solved] 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 applying transformation rule (C) using substitution {C==1,D==0,A==0,B==-n} 5.37/2.53 5.37/2.53 resulting limit problem: 5.37/2.53 5.37/2.53 [solved] 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Solution: 5.37/2.53 5.37/2.53 C / 1 5.37/2.53 5.37/2.53 D / 0 5.37/2.53 5.37/2.53 A / 0 5.37/2.53 5.37/2.53 B / -n 5.37/2.53 5.37/2.53 Resulting cost 1+n has complexity: Poly(n^1) 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Found new complexity Poly(n^1). 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 Obtained the following overall complexity (w.r.t. the length of the input n): 5.37/2.53 5.37/2.53 Complexity: Poly(n^1) 5.37/2.53 5.37/2.53 Cpx degree: 1 5.37/2.53 5.37/2.53 Solved cost: 1+n 5.37/2.53 5.37/2.53 Rule cost: 1+A-B 5.37/2.53 5.37/2.53 Rule guard: [ A>=1+B && C>=1+D ] 5.37/2.53 5.37/2.53 5.37/2.53 5.37/2.53 WORST_CASE(Omega(n^1),?) 5.37/2.53 5.37/2.53 5.37/2.53 ---------------------------------------- 5.37/2.53 5.37/2.53 (4) 5.37/2.53 BOUNDS(n^1, INF) 5.37/2.55 EOF