4.45/2.10 WORST_CASE(Omega(n^1), O(n^1)) 4.45/2.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.45/2.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.45/2.11 4.45/2.11 4.45/2.11 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). 4.45/2.11 4.45/2.11 (0) CpxIntTrs 4.45/2.11 (1) Koat Proof [FINISHED, 11 ms] 4.45/2.11 (2) BOUNDS(1, n^1) 4.45/2.11 (3) Loat Proof [FINISHED, 549 ms] 4.45/2.11 (4) BOUNDS(n^1, INF) 4.45/2.11 4.45/2.11 4.45/2.11 ---------------------------------------- 4.45/2.11 4.45/2.11 (0) 4.45/2.11 Obligation: 4.45/2.11 Complexity Int TRS consisting of the following rules: 4.45/2.11 evalSequentialSinglestart(A, B) -> Com_1(evalSequentialSingleentryin(A, B)) :|: TRUE 4.45/2.11 evalSequentialSingleentryin(A, B) -> Com_1(evalSequentialSinglebb1in(0, B)) :|: TRUE 4.45/2.11 evalSequentialSinglebb1in(A, B) -> Com_1(evalSequentialSinglebb5in(A, B)) :|: A >= B 4.45/2.11 evalSequentialSinglebb1in(A, B) -> Com_1(evalSequentialSinglebb2in(A, B)) :|: B >= A + 1 4.45/2.11 evalSequentialSinglebb2in(A, B) -> Com_1(evalSequentialSinglebbin(A, B)) :|: 0 >= C + 1 4.45/2.11 evalSequentialSinglebb2in(A, B) -> Com_1(evalSequentialSinglebbin(A, B)) :|: C >= 1 4.45/2.11 evalSequentialSinglebb2in(A, B) -> Com_1(evalSequentialSinglebb5in(A, B)) :|: TRUE 4.45/2.11 evalSequentialSinglebbin(A, B) -> Com_1(evalSequentialSinglebb1in(A + 1, B)) :|: TRUE 4.45/2.11 evalSequentialSinglebb5in(A, B) -> Com_1(evalSequentialSinglebb4in(A, B)) :|: B >= A + 1 4.45/2.11 evalSequentialSinglebb5in(A, B) -> Com_1(evalSequentialSinglereturnin(A, B)) :|: A >= B 4.45/2.11 evalSequentialSinglebb4in(A, B) -> Com_1(evalSequentialSinglebb5in(A + 1, B)) :|: TRUE 4.45/2.11 evalSequentialSinglereturnin(A, B) -> Com_1(evalSequentialSinglestop(A, B)) :|: TRUE 4.45/2.11 4.45/2.11 The start-symbols are:[evalSequentialSinglestart_2] 4.45/2.11 4.45/2.11 4.45/2.11 ---------------------------------------- 4.45/2.11 4.45/2.11 (1) Koat Proof (FINISHED) 4.45/2.11 YES(?, 7*ar_1 + 21) 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Initial complexity problem: 4.45/2.11 4.45/2.11 1: T: 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglestart(ar_0, ar_1) -> Com_1(evalSequentialSingleentryin(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSingleentryin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ 0 >= c + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ c >= 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebbin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb4in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglereturnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb4in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglereturnin(ar_0, ar_1) -> Com_1(evalSequentialSinglestop(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalSequentialSinglestart(ar_0, ar_1)) [ 0 <= 0 ] 4.45/2.11 4.45/2.11 start location: koat_start 4.45/2.11 4.45/2.11 leaf cost: 0 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Repeatedly propagating knowledge in problem 1 produces the following problem: 4.45/2.11 4.45/2.11 2: T: 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 1) evalSequentialSinglestart(ar_0, ar_1) -> Com_1(evalSequentialSingleentryin(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 1) evalSequentialSingleentryin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ 0 >= c + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ c >= 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebbin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb4in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglereturnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb4in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglereturnin(ar_0, ar_1) -> Com_1(evalSequentialSinglestop(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalSequentialSinglestart(ar_0, ar_1)) [ 0 <= 0 ] 4.45/2.11 4.45/2.11 start location: koat_start 4.45/2.11 4.45/2.11 leaf cost: 0 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 A polynomial rank function with 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglestart) = 3 4.45/2.11 4.45/2.11 Pol(evalSequentialSingleentryin) = 3 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebb1in) = 3 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebb5in) = 2 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebb2in) = 3 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebbin) = 3 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebb4in) = 2 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglereturnin) = 1 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglestop) = 0 4.45/2.11 4.45/2.11 Pol(koat_start) = 3 4.45/2.11 4.45/2.11 orients all transitions weakly and the transitions 4.45/2.11 4.45/2.11 evalSequentialSinglereturnin(ar_0, ar_1) -> Com_1(evalSequentialSinglestop(ar_0, ar_1)) 4.45/2.11 4.45/2.11 evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglereturnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) 4.45/2.11 4.45/2.11 evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 strictly and produces the following problem: 4.45/2.11 4.45/2.11 3: T: 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 1) evalSequentialSinglestart(ar_0, ar_1) -> Com_1(evalSequentialSingleentryin(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 1) evalSequentialSingleentryin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ 0 >= c + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ c >= 1 ] 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebbin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb4in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglereturnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb4in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglereturnin(ar_0, ar_1) -> Com_1(evalSequentialSinglestop(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalSequentialSinglestart(ar_0, ar_1)) [ 0 <= 0 ] 4.45/2.11 4.45/2.11 start location: koat_start 4.45/2.11 4.45/2.11 leaf cost: 0 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 A polynomial rank function with 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglestart) = V_2 + 1 4.45/2.11 4.45/2.11 Pol(evalSequentialSingleentryin) = V_2 + 1 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebb1in) = -V_1 + V_2 + 1 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebb5in) = -V_1 + V_2 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebb2in) = -V_1 + V_2 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebbin) = -V_1 + V_2 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglebb4in) = -V_1 + V_2 - 1 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglereturnin) = -V_1 + V_2 4.45/2.11 4.45/2.11 Pol(evalSequentialSinglestop) = -V_1 + V_2 4.45/2.11 4.45/2.11 Pol(koat_start) = V_2 + 1 4.45/2.11 4.45/2.11 orients all transitions weakly and the transitions 4.45/2.11 4.45/2.11 evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb4in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 strictly and produces the following problem: 4.45/2.11 4.45/2.11 4: T: 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 1) evalSequentialSinglestart(ar_0, ar_1) -> Com_1(evalSequentialSingleentryin(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 1) evalSequentialSingleentryin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ar_1 + 1, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ 0 >= c + 1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ c >= 1 ] 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebbin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ar_1 + 1, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb4in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglereturnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ?, Cost: 1) evalSequentialSinglebb4in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglereturnin(ar_0, ar_1) -> Com_1(evalSequentialSinglestop(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalSequentialSinglestart(ar_0, ar_1)) [ 0 <= 0 ] 4.45/2.11 4.45/2.11 start location: koat_start 4.45/2.11 4.45/2.11 leaf cost: 0 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Repeatedly propagating knowledge in problem 4 produces the following problem: 4.45/2.11 4.45/2.11 5: T: 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 1) evalSequentialSinglestart(ar_0, ar_1) -> Com_1(evalSequentialSingleentryin(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 1) evalSequentialSingleentryin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ar_1 + 1, Cost: 1) evalSequentialSinglebb1in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: ar_1 + 1, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ 0 >= c + 1 ] 4.45/2.11 4.45/2.11 (Comp: ar_1 + 1, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebbin(ar_0, ar_1)) [ c >= 1 ] 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglebb2in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 2*ar_1 + 2, Cost: 1) evalSequentialSinglebbin(ar_0, ar_1) -> Com_1(evalSequentialSinglebb1in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: ar_1 + 1, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb4in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ] 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglebb5in(ar_0, ar_1) -> Com_1(evalSequentialSinglereturnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] 4.45/2.11 4.45/2.11 (Comp: ar_1 + 1, Cost: 1) evalSequentialSinglebb4in(ar_0, ar_1) -> Com_1(evalSequentialSinglebb5in(ar_0 + 1, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 3, Cost: 1) evalSequentialSinglereturnin(ar_0, ar_1) -> Com_1(evalSequentialSinglestop(ar_0, ar_1)) 4.45/2.11 4.45/2.11 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalSequentialSinglestart(ar_0, ar_1)) [ 0 <= 0 ] 4.45/2.11 4.45/2.11 start location: koat_start 4.45/2.11 4.45/2.11 leaf cost: 0 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Complexity upper bound 7*ar_1 + 21 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Time: 0.079 sec (SMT: 0.071 sec) 4.45/2.11 4.45/2.11 4.45/2.11 ---------------------------------------- 4.45/2.11 4.45/2.11 (2) 4.45/2.11 BOUNDS(1, n^1) 4.45/2.11 4.45/2.11 ---------------------------------------- 4.45/2.11 4.45/2.11 (3) Loat Proof (FINISHED) 4.45/2.11 4.45/2.11 4.45/2.11 ### Pre-processing the ITS problem ### 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Initial linear ITS problem 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 0: evalSequentialSinglestart -> evalSequentialSingleentryin : [], cost: 1 4.45/2.11 4.45/2.11 1: evalSequentialSingleentryin -> evalSequentialSinglebb1in : A'=0, [], cost: 1 4.45/2.11 4.45/2.11 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 4.45/2.11 4.45/2.11 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 4: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [ 0>=1+free ], cost: 1 4.45/2.11 4.45/2.11 5: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [ free_1>=1 ], cost: 1 4.45/2.11 4.45/2.11 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 4.45/2.11 4.45/2.11 7: evalSequentialSinglebbin -> evalSequentialSinglebb1in : A'=1+A, [], cost: 1 4.45/2.11 4.45/2.11 8: evalSequentialSinglebb5in -> evalSequentialSinglebb4in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 9: evalSequentialSinglebb5in -> evalSequentialSinglereturnin : [ A>=B ], cost: 1 4.45/2.11 4.45/2.11 10: evalSequentialSinglebb4in -> evalSequentialSinglebb5in : A'=1+A, [], cost: 1 4.45/2.11 4.45/2.11 11: evalSequentialSinglereturnin -> evalSequentialSinglestop : [], cost: 1 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Removed unreachable and leaf rules: 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 0: evalSequentialSinglestart -> evalSequentialSingleentryin : [], cost: 1 4.45/2.11 4.45/2.11 1: evalSequentialSingleentryin -> evalSequentialSinglebb1in : A'=0, [], cost: 1 4.45/2.11 4.45/2.11 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 4.45/2.11 4.45/2.11 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 4: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [ 0>=1+free ], cost: 1 4.45/2.11 4.45/2.11 5: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [ free_1>=1 ], cost: 1 4.45/2.11 4.45/2.11 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 4.45/2.11 4.45/2.11 7: evalSequentialSinglebbin -> evalSequentialSinglebb1in : A'=1+A, [], cost: 1 4.45/2.11 4.45/2.11 8: evalSequentialSinglebb5in -> evalSequentialSinglebb4in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 10: evalSequentialSinglebb4in -> evalSequentialSinglebb5in : A'=1+A, [], cost: 1 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Simplified all rules, resulting in: 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 0: evalSequentialSinglestart -> evalSequentialSingleentryin : [], cost: 1 4.45/2.11 4.45/2.11 1: evalSequentialSingleentryin -> evalSequentialSinglebb1in : A'=0, [], cost: 1 4.45/2.11 4.45/2.11 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 4.45/2.11 4.45/2.11 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 5: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [], cost: 1 4.45/2.11 4.45/2.11 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 4.45/2.11 4.45/2.11 7: evalSequentialSinglebbin -> evalSequentialSinglebb1in : A'=1+A, [], cost: 1 4.45/2.11 4.45/2.11 8: evalSequentialSinglebb5in -> evalSequentialSinglebb4in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 10: evalSequentialSinglebb4in -> evalSequentialSinglebb5in : A'=1+A, [], cost: 1 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 ### Simplification by acceleration and chaining ### 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Eliminated locations (on linear paths): 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 4.45/2.11 4.45/2.11 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 4.45/2.11 4.45/2.11 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 4.45/2.11 4.45/2.11 13: evalSequentialSinglebb2in -> evalSequentialSinglebb1in : A'=1+A, [], cost: 2 4.45/2.11 4.45/2.11 14: evalSequentialSinglebb5in -> evalSequentialSinglebb5in : A'=1+A, [ B>=1+A ], cost: 2 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Accelerating simple loops of location 5. 4.45/2.11 4.45/2.11 Accelerating the following rules: 4.45/2.11 4.45/2.11 14: evalSequentialSinglebb5in -> evalSequentialSinglebb5in : A'=1+A, [ B>=1+A ], cost: 2 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Accelerated rule 14 with metering function -A+B, yielding the new rule 15. 4.45/2.11 4.45/2.11 Removing the simple loops: 14. 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Accelerated all simple loops using metering functions (where possible): 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 4.45/2.11 4.45/2.11 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 4.45/2.11 4.45/2.11 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 4.45/2.11 4.45/2.11 13: evalSequentialSinglebb2in -> evalSequentialSinglebb1in : A'=1+A, [], cost: 2 4.45/2.11 4.45/2.11 15: evalSequentialSinglebb5in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: -2*A+2*B 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Chained accelerated rules (with incoming rules): 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 4.45/2.11 4.45/2.11 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 4.45/2.11 4.45/2.11 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 4.45/2.11 4.45/2.11 13: evalSequentialSinglebb2in -> evalSequentialSinglebb1in : A'=1+A, [], cost: 2 4.45/2.11 4.45/2.11 16: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 1-2*A+2*B 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Removed unreachable locations (and leaf rules with constant cost): 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 4.45/2.11 4.45/2.11 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 4.45/2.11 4.45/2.11 13: evalSequentialSinglebb2in -> evalSequentialSinglebb1in : A'=1+A, [], cost: 2 4.45/2.11 4.45/2.11 16: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 1-2*A+2*B 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Eliminated locations (on tree-shaped paths): 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 4.45/2.11 4.45/2.11 17: evalSequentialSinglebb1in -> evalSequentialSinglebb1in : A'=1+A, [ B>=1+A ], cost: 3 4.45/2.11 4.45/2.11 18: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 2-2*A+2*B 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Accelerating simple loops of location 2. 4.45/2.11 4.45/2.11 Accelerating the following rules: 4.45/2.11 4.45/2.11 17: evalSequentialSinglebb1in -> evalSequentialSinglebb1in : A'=1+A, [ B>=1+A ], cost: 3 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Accelerated rule 17 with metering function -A+B, yielding the new rule 19. 4.45/2.11 4.45/2.11 Removing the simple loops: 17. 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Accelerated all simple loops using metering functions (where possible): 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 4.45/2.11 4.45/2.11 18: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 2-2*A+2*B 4.45/2.11 4.45/2.11 19: evalSequentialSinglebb1in -> evalSequentialSinglebb1in : A'=B, [ B>=1+A ], cost: -3*A+3*B 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Chained accelerated rules (with incoming rules): 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 4.45/2.11 4.45/2.11 20: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=B, [ B>=1 ], cost: 2+3*B 4.45/2.11 4.45/2.11 18: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 2-2*A+2*B 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Eliminated locations (on tree-shaped paths): 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 21: evalSequentialSinglestart -> evalSequentialSinglebb5in : A'=B, [ B>=1 ], cost: 4+2*B 4.45/2.11 4.45/2.11 22: evalSequentialSinglestart -> [11] : [ B>=1 ], cost: 2+3*B 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 ### Computing asymptotic complexity ### 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Fully simplified ITS problem 4.45/2.11 4.45/2.11 Start location: evalSequentialSinglestart 4.45/2.11 4.45/2.11 21: evalSequentialSinglestart -> evalSequentialSinglebb5in : A'=B, [ B>=1 ], cost: 4+2*B 4.45/2.11 4.45/2.11 22: evalSequentialSinglestart -> [11] : [ B>=1 ], cost: 2+3*B 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Computing asymptotic complexity for rule 21 4.45/2.11 4.45/2.11 Solved the limit problem by the following transformations: 4.45/2.11 4.45/2.11 Created initial limit problem: 4.45/2.11 4.45/2.11 4+2*B (+), B (+/+!) [not solved] 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 removing all constraints (solved by SMT) 4.45/2.11 4.45/2.11 resulting limit problem: [solved] 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 applying transformation rule (C) using substitution {B==n} 4.45/2.11 4.45/2.11 resulting limit problem: 4.45/2.11 4.45/2.11 [solved] 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Solution: 4.45/2.11 4.45/2.11 B / n 4.45/2.11 4.45/2.11 Resulting cost 4+2*n has complexity: Poly(n^1) 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Found new complexity Poly(n^1). 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 Obtained the following overall complexity (w.r.t. the length of the input n): 4.45/2.11 4.45/2.11 Complexity: Poly(n^1) 4.45/2.11 4.45/2.11 Cpx degree: 1 4.45/2.11 4.45/2.11 Solved cost: 4+2*n 4.45/2.11 4.45/2.11 Rule cost: 4+2*B 4.45/2.11 4.45/2.11 Rule guard: [ B>=1 ] 4.45/2.11 4.45/2.11 4.45/2.11 4.45/2.11 WORST_CASE(Omega(n^1),?) 4.45/2.11 4.45/2.11 4.45/2.11 ---------------------------------------- 4.45/2.11 4.45/2.11 (4) 4.45/2.11 BOUNDS(n^1, INF) 4.52/2.12 EOF