Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Complexity_ITS 2019-03-21 04.46 pair #429989784
details
property
value
status
complete
benchmark
a.03.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n140.star.cs.uiowa.edu
space
pasta
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
95.6709 seconds
cpu usage
103.943
user time
102.492
system time
1.45179
max virtual memory
1.8753868E7
max residence set size
315204.0
stage attributes
key
value
starexec-result
WORST_CASE(Omega(n^1), O(n^2))
output
103.82/95.62 WORST_CASE(Omega(n^1), O(n^2)) 103.82/95.64 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 103.82/95.64 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 103.82/95.64 103.82/95.64 103.82/95.64 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(2, 2 * Arg_0) + max(2, 2 * Arg_0) * nat(max(8, -4 + 4 * Arg_1, 4 * Arg_1) + max(-8, min(-8, 8 + -8 * Arg_0))) + 2 * max(2, 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, 2 * Arg_0) * max(5, -1 + 2 * Arg_1, 1 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + 2 * max(2, -2 + 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, -2 + 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, -2 + 2 * Arg_0) * max(5, -1 + 2 * Arg_1, 1 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + max(2, -2 + 2 * Arg_0) + max(2, -2 + 2 * Arg_0) * nat(max(-8, min(-8, 8 + -8 * Arg_0)) + max(8, -4 + 4 * Arg_1, 4 * Arg_1)) + nat(1 + 2 * Arg_1) + nat(2 * Arg_1 + max(2 + -2 * Arg_0, -2)) + nat(4 * Arg_1) + nat(-1 + 2 * Arg_1) + nat(-1 + Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1 + max(-8, -8 * Arg_0)) + nat(-2 + 2 * Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1) + nat(Arg_1 + max(2 + -2 * Arg_0, -2)) + max(2 * Arg_1, 2) + nat(-1 + Arg_1) * max(-2 + Arg_1, -3 + Arg_1, 0) + nat(-1 + Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(-1 + Arg_1) * max(-12 + 4 * Arg_1, -8 + 4 * Arg_1, 0) + nat(Arg_1) * max(-2 + Arg_1, -3 + Arg_1, 0) + nat(Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(Arg_1) * max(-12 + 4 * Arg_1, -8 + 4 * Arg_1, 0) + nat(2 * Arg_1) + nat(4 * Arg_1 + max(-8, 8 + -8 * Arg_0))). 103.82/95.64 103.82/95.64 (0) CpxIntTrs 103.82/95.64 (1) Koat2 Proof [FINISHED, 2727 ms] 103.82/95.64 (2) BOUNDS(1, max(2, 2 * Arg_0) + max(2, 2 * Arg_0) * nat(max(8, -4 + 4 * Arg_1, 4 * Arg_1) + max(-8, min(-8, 8 + -8 * Arg_0))) + 2 * max(2, 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, 2 * Arg_0) * max(5, -1 + 2 * Arg_1, 1 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + 2 * max(2, -2 + 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, -2 + 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, -2 + 2 * Arg_0) * max(5, -1 + 2 * Arg_1, 1 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + max(2, -2 + 2 * Arg_0) + max(2, -2 + 2 * Arg_0) * nat(max(-8, min(-8, 8 + -8 * Arg_0)) + max(8, -4 + 4 * Arg_1, 4 * Arg_1)) + nat(1 + 2 * Arg_1) + nat(2 * Arg_1 + max(2 + -2 * Arg_0, -2)) + nat(4 * Arg_1) + nat(-1 + 2 * Arg_1) + nat(-1 + Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1 + max(-8, -8 * Arg_0)) + nat(-2 + 2 * Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1) + nat(Arg_1 + max(2 + -2 * Arg_0, -2)) + max(2 * Arg_1, 2) + nat(-1 + Arg_1) * max(-2 + Arg_1, -3 + Arg_1, 0) + nat(-1 + Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(-1 + Arg_1) * max(-12 + 4 * Arg_1, -8 + 4 * Arg_1, 0) + nat(Arg_1) * max(-2 + Arg_1, -3 + Arg_1, 0) + nat(Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(Arg_1) * max(-12 + 4 * Arg_1, -8 + 4 * Arg_1, 0) + nat(2 * Arg_1) + nat(4 * Arg_1 + max(-8, 8 + -8 * Arg_0))) 103.82/95.64 (3) Loat Proof [FINISHED, 94.1 s] 103.82/95.64 (4) BOUNDS(n^1, INF) 103.82/95.64 103.82/95.64 103.82/95.64 ---------------------------------------- 103.82/95.64 103.82/95.64 (0) 103.82/95.64 Obligation: 103.82/95.64 Complexity Int TRS consisting of the following rules: 103.82/95.64 eval1(A, B, C, D) -> Com_1(eval2(A - 1, B, C, D)) :|: A >= 2 103.82/95.64 eval1(A, B, C, D) -> Com_1(eval2(A, B - 1, C, D)) :|: 1 >= A 103.82/95.64 eval2(A, B, C, D) -> Com_1(eval3(A, B, A, 2 * A)) :|: B >= 2 103.82/95.64 eval3(A, B, C, D) -> Com_1(eval4(A, B, C, D)) :|: B >= D && B >= 1 + D 103.82/95.64 eval3(A, B, C, D) -> Com_1(eval4(A, B, C, D + 1)) :|: B >= D && B >= 1 + D 103.82/95.64 eval3(A, B, C, D) -> Com_1(eval3(A, B, D, 2 * D)) :|: B >= D && B >= 1 + D && D >= 1 103.82/95.64 eval3(A, B, C, D) -> Com_1(eval3(A, B, D + 1, 2 * D + 2)) :|: B >= D && B >= 1 + D && D >= 1 103.82/95.64 eval3(A, B, C, D) -> Com_1(eval4(A, B, C, D)) :|: B >= D && B <= D 103.82/95.64 eval3(A, B, C, D) -> Com_1(eval3(A, B, D, 2 * D)) :|: D >= 1 && B >= D && B <= D 103.82/95.64 eval4(A, B, C, D) -> Com_1(eval2(A - 1, B, C, D)) :|: A >= 2 && A >= 1 && B >= 2 103.82/95.64 eval4(A, B, C, D) -> Com_1(eval2(A, B - 1, C, D)) :|: B >= 2 && A >= 1 && A <= 1 103.82/95.64 103.82/95.64 The start-symbols are:[eval1_4] 103.82/95.64 103.82/95.64 103.82/95.64 ---------------------------------------- 103.82/95.64 103.82/95.64 (1) Koat2 Proof (FINISHED) 103.82/95.64 YES( ?, 2+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+max([0, 1+2*Arg_1])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+2*max([Arg_1, -1+Arg_1])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, Arg_1])+max([2, 2*Arg_0])+max([0, 2*Arg_1])+max([0, -1+Arg_1])+max([2, 2*(-1+Arg_0)])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([5, 1+2*max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-2, -2*max([1, -1+Arg_0])])+max([4, 2*max([Arg_1, -1+Arg_1])])])+max([0, 1+2*(-1+Arg_1)])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 2*(-1+Arg_1)+max([-2, -2*Arg_0])])+max([0, 2*(-1+Arg_1)])+max([0, -1+Arg_1])+max([0, 2*(-1+Arg_1)])+max([0, Arg_1]) {O(n^2)}) 103.82/95.64 103.82/95.64 103.82/95.64 103.82/95.64 Initial Complexity Problem: 103.82/95.64 103.82/95.64 Start: eval1 103.82/95.64 103.82/95.64 Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3 103.82/95.64 103.82/95.64 Temp_Vars: 103.82/95.64 103.82/95.64 Locations: eval1, eval2, eval3, eval4 103.82/95.64 103.82/95.64 Transitions: 103.82/95.64 103.82/95.64 eval1(Arg_0,Arg_1,Arg_2,Arg_3) -> eval2(Arg_0-1,Arg_1,Arg_2,Arg_3):|:2 <= Arg_0 103.82/95.64 103.82/95.64 eval1(Arg_0,Arg_1,Arg_2,Arg_3) -> eval2(Arg_0,Arg_1-1,Arg_2,Arg_3):|:Arg_0 <= 1 103.82/95.64 103.82/95.64 eval2(Arg_0,Arg_1,Arg_2,Arg_3) -> eval3(Arg_0,Arg_1,Arg_0,(2)*Arg_0):|:2 <= Arg_1 103.82/95.64 103.82/95.64 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval3(Arg_0,Arg_1,Arg_3,(2)*Arg_3):|:2 <= Arg_1 && Arg_3 <= Arg_1 && 1+Arg_3 <= Arg_1 && 1 <= Arg_3 103.82/95.64 103.82/95.64 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval3(Arg_0,Arg_1,Arg_3+1,(2)*Arg_3+2):|:2 <= Arg_1 && Arg_3 <= Arg_1 && 1+Arg_3 <= Arg_1 && 1 <= Arg_3 103.82/95.64 103.82/95.64 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval3(Arg_0,Arg_1,Arg_3,(2)*Arg_3):|:2 <= Arg_1 && 1 <= Arg_3 && Arg_1 <= Arg_3 && Arg_3 <= Arg_1 103.82/95.64 103.82/95.64 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval4(Arg_0,Arg_1,Arg_2,Arg_3):|:2 <= Arg_1 && Arg_3 <= Arg_1 && 1+Arg_3 <= Arg_1 103.82/95.64 103.82/95.64 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval4(Arg_0,Arg_1,Arg_2,Arg_3+1):|:2 <= Arg_1 && Arg_3 <= Arg_1 && 1+Arg_3 <= Arg_1 103.82/95.64 103.82/95.64 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval4(Arg_0,Arg_1,Arg_2,Arg_3):|:2 <= Arg_1 && Arg_1 <= Arg_3 && Arg_3 <= Arg_1 103.82/95.64 103.82/95.64 eval4(Arg_0,Arg_1,Arg_2,Arg_3) -> eval2(Arg_0-1,Arg_1,Arg_2,Arg_3):|:2 <= Arg_1 && 2 <= Arg_0 && 1 <= Arg_0 && 2 <= Arg_1 103.82/95.64 103.82/95.64 eval4(Arg_0,Arg_1,Arg_2,Arg_3) -> eval2(Arg_0,Arg_1-1,Arg_2,Arg_3):|:2 <= Arg_1 && 2 <= Arg_1 && Arg_0 <= 1 && 1 <= Arg_0 103.82/95.64 103.82/95.64 103.82/95.64 103.82/95.64 Timebounds: 103.82/95.64 103.82/95.64 Overall timebound: 2+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+max([0, 1+2*Arg_1])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+2*max([Arg_1, -1+Arg_1])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, Arg_1])+max([2, 2*Arg_0])+max([0, 2*Arg_1])+max([0, -1+Arg_1])+max([2, 2*(-1+Arg_0)])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([5, 1+2*max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-2, -2*max([1, -1+Arg_0])])+max([4, 2*max([Arg_1, -1+Arg_1])])])+max([0, 1+2*(-1+Arg_1)])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 2*(-1+Arg_1)+max([-2, -2*Arg_0])])+max([0, 2*(-1+Arg_1)])+max([0, -1+Arg_1])+max([0, 2*(-1+Arg_1)])+max([0, Arg_1]) {O(n^2)} 103.82/95.64 103.82/95.64 0: eval1->eval2: 1 {O(1)} 103.82/95.64 103.82/95.64 1: eval1->eval2: 1 {O(1)} 103.82/95.64 103.82/95.64 2: eval2->eval3: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([5, 1+2*max([Arg_1, -1+Arg_1])])+max([0, 1+2*(-1+Arg_1)])+max([0, 1+2*Arg_1]) {O(n^2)} 103.82/95.64 103.82/95.64 3: eval3->eval4: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*(-1+Arg_1)])+max([0, 2*Arg_1]) {O(n^2)} 103.82/95.64 103.82/95.64 4: eval3->eval4: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])])+max([0, -1+Arg_1])+max([0, Arg_1]) {O(n^2)} 103.82/95.64 103.82/95.64 5: eval3->eval3: (max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]) {O(n^2)} 103.82/95.64 103.82/95.64 6: eval3->eval3: (max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]) {O(n^2)} 103.82/95.64 103.82/95.64 7: eval3->eval4: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*(-1+Arg_1)])+max([0, 2*Arg_1]) {O(n^2)} 103.82/95.64 103.82/95.64 8: eval3->eval3: (max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+2*max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-2, -2*max([1, -1+Arg_0])])+max([4, 2*max([Arg_1, -1+Arg_1])])])+max([0, 2*(-1+Arg_1)+max([-2, -2*Arg_0])])+max([0, 2*Arg_1+max([-2, -2*(-1+Arg_0)])]) {O(n^2)} 103.82/95.64 103.82/95.64 9: eval4->eval2: max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]) {O(n)}
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Complexity_ITS 2019-03-21 04.46