Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Complexity_ITS 2019-03-21 04.46 pair #429990504
details
property
value
status
complete
benchmark
ludcmp.c.i.ludcmp.pl.t2.nor.t2.rlgfixed.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n040.star.cs.uiowa.edu
space
T2
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
20.3248 seconds
cpu usage
39.3692
user time
38.0952
system time
1.274
max virtual memory
1.8906796E7
max residence set size
309452.0
stage attributes
key
value
starexec-result
WORST_CASE(Omega(n^1), O(n^1))
output
39.21/20.28 WORST_CASE(Omega(n^1), O(n^1)) 39.21/20.30 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 39.21/20.30 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 39.21/20.30 39.21/20.30 39.21/20.30 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, nat(max(4 * Arg_1 + nat(8 + 8 * Arg_0 + -8 * Arg_1), 4 * Arg_1) + max(-4 * Arg_3, min(-4 * Arg_3, -4 * Arg_3 + min(-8 + -8 * Arg_0 + 8 * Arg_3, 0)))) + nat(4 + 4 * Arg_0 + -4 * Arg_3) + max(1, 2 + Arg_0 + -1 * Arg_3) + max(2, 3 + 3 * Arg_0 + max(min(-3 * Arg_3, -3 * Arg_3 + min(-6 + -6 * Arg_0 + 6 * Arg_3, 0)), -3 * Arg_3)) + nat(3 + 3 * Arg_0 + -3 * Arg_1) + nat(-3 * Arg_3 + max(3 * Arg_1 + nat(6 + 6 * Arg_0 + -6 * Arg_1), 3 * Arg_1)) + nat(2 * Arg_0 + -2 * Arg_3) + nat(-1 * Arg_7 + max(Arg_1 + nat(2 + 2 * Arg_0 + -2 * Arg_1), Arg_1)) + nat(1 + 2 * Arg_0 + max(min(-2 * Arg_3, -2 * Arg_3 + min(-4 + -4 * Arg_0 + 4 * Arg_3, 0)), -2 * Arg_3)) + nat(max(5 * Arg_1 + nat(10 + 10 * Arg_0 + -10 * Arg_1), 5 * Arg_1) + max(-5 * Arg_3, min(-5 * Arg_3, -5 * Arg_3 + min(-10 + -10 * Arg_0 + 10 * Arg_3, 0))))). 39.21/20.30 39.21/20.30 (0) CpxIntTrs 39.21/20.30 (1) Koat2 Proof [FINISHED, 14.7 s] 39.21/20.30 (2) BOUNDS(1, nat(max(4 * Arg_1 + nat(8 + 8 * Arg_0 + -8 * Arg_1), 4 * Arg_1) + max(-4 * Arg_3, min(-4 * Arg_3, -4 * Arg_3 + min(-8 + -8 * Arg_0 + 8 * Arg_3, 0)))) + nat(4 + 4 * Arg_0 + -4 * Arg_3) + max(1, 2 + Arg_0 + -1 * Arg_3) + max(2, 3 + 3 * Arg_0 + max(min(-3 * Arg_3, -3 * Arg_3 + min(-6 + -6 * Arg_0 + 6 * Arg_3, 0)), -3 * Arg_3)) + nat(3 + 3 * Arg_0 + -3 * Arg_1) + nat(-3 * Arg_3 + max(3 * Arg_1 + nat(6 + 6 * Arg_0 + -6 * Arg_1), 3 * Arg_1)) + nat(2 * Arg_0 + -2 * Arg_3) + nat(-1 * Arg_7 + max(Arg_1 + nat(2 + 2 * Arg_0 + -2 * Arg_1), Arg_1)) + nat(1 + 2 * Arg_0 + max(min(-2 * Arg_3, -2 * Arg_3 + min(-4 + -4 * Arg_0 + 4 * Arg_3, 0)), -2 * Arg_3)) + nat(max(5 * Arg_1 + nat(10 + 10 * Arg_0 + -10 * Arg_1), 5 * Arg_1) + max(-5 * Arg_3, min(-5 * Arg_3, -5 * Arg_3 + min(-10 + -10 * Arg_0 + 10 * Arg_3, 0))))) 39.21/20.30 (3) Loat Proof [FINISHED, 18.5 s] 39.21/20.30 (4) BOUNDS(n^1, INF) 39.21/20.30 39.21/20.30 39.21/20.30 ---------------------------------------- 39.21/20.30 39.21/20.30 (0) 39.21/20.30 Obligation: 39.21/20.30 Complexity Int TRS consisting of the following rules: 39.21/20.30 f69(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f71(A, B, C, D, E, F, G, H, I, J, K)) :|: 0 >= L + 1 39.21/20.30 f69(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f71(A, B, C, D, E, F, G, H, I, J, K)) :|: L >= 1 39.21/20.30 f2(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f5(A, B, C, D, E, F, G, H, I, J, K)) :|: TRUE 39.21/20.30 f5(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f9(A, B, 0, D, E, F, G, H, I, J, K)) :|: A >= B 39.21/20.30 f9(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f9(A, B, C, D + 1, L, L, G, H, I, J, K)) :|: C >= L && A >= D 39.21/20.30 f9(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f9(A, B, L, D + 1, L, L, G, H, I, J, K)) :|: L >= 1 + C && A >= D 39.21/20.30 f23(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f26(A, B, C, D, E, F, G, H, I, J, K)) :|: A >= D 39.21/20.30 f26(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f30(A, B, C, D, E, F, L, H, I, J, K)) :|: D >= B + 1 39.21/20.30 f30(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f30(A, B, C, D, E, F, L, H + 1, I, J, K)) :|: B >= H + 1 39.21/20.30 f40(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f44(A, B, C, D, E, F, L, H, I, J, K)) :|: A >= B 39.21/20.30 f44(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f44(A, B, C, D, E, F, L, H + 1, I, J, K)) :|: D >= H + 1 39.21/20.30 f59(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f59(A, B, C, D, E, F, G, H + 1, L, J, K)) :|: A >= H 39.21/20.30 f69(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f71(A, B, C, D, E, F, G, H, I, J, K)) :|: TRUE 39.21/20.30 f71(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f74(A, B, C, D, E, F, G, H, L, J, K)) :|: A >= D + 1 39.21/20.30 f71(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f74(A, B, C, D, E, F, G, H, L, J, K)) :|: D >= 1 + A 39.21/20.30 f74(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f74(A, B + 1, C, D, E, F, G, H, I, J, K)) :|: A >= B 39.21/20.30 f71(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f23(A, B, C, A + 1, E, F, G, H, I, J, K)) :|: A >= D && A <= D 39.21/20.30 f74(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f23(A, B, C, D + 1, E, F, G, H, I, J, K)) :|: B >= 1 + A 39.21/20.30 f59(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f69(A, B, C, D, E, F, G, H, I, J, K)) :|: H >= 1 + A 39.21/20.30 f44(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f40(A, B + 1, C, D, E, F, G, H, M, L, K)) :|: C >= M + 1 && H >= D 39.21/20.30 f44(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f40(A, B + 1, L, D, E, F, G, H, L, M, B)) :|: L >= C && H >= D 39.21/20.30 f40(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K)) :|: B >= 1 + A && K >= D + 1 39.21/20.30 f40(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K)) :|: B >= 1 + A && D >= 1 + K 39.21/20.30 f40(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f69(A, B, C, D, E, F, G, H, I, J, D)) :|: B >= 1 + A && D >= K && D <= K 39.21/20.30 f30(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f26(A, B + 1, C, D, E, F, G, H, I, J, K)) :|: H >= B 39.21/20.30 f26(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f40(A, B, 0, D, E, F, G, H, I, J, K)) :|: B >= D 39.21/20.30 f23(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, K)) :|: D >= 1 + A 39.21/20.30 f9(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f5(A, B + 1, C, D, E, F, G, H, I, J, K)) :|: 0 >= C + 1 && D >= 1 + A 39.21/20.30 f9(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f5(A, B + 1, C, D, E, F, G, H, I, J, K)) :|: C >= 1 && D >= 1 + A 39.21/20.30 f9(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f5(A, B + 1, 0, D, E, F, G, H, I, J, K)) :|: D >= 1 + A && C >= 0 && C <= 0 39.21/20.30 f5(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f23(A, B, C, D, E, F, G, H, I, J, K)) :|: B >= 1 + A 39.21/20.30 39.21/20.30 The start-symbols are:[f2_11] 39.21/20.30 39.21/20.30 39.21/20.30 ---------------------------------------- 39.21/20.30 39.21/20.30 (1) Koat2 Proof (FINISHED) 39.21/20.30 YES( ?, 1+max([0, 1+Arg_0-Arg_3])+max([0, max([4*Arg_1, 4*max([Arg_1, Arg_1+2*max([0, 1+Arg_0-Arg_1])])])+max([-4*Arg_3, -4*max([Arg_3, Arg_3+2*max([0, 1+Arg_0-Arg_3])])])])+max([0, 1+Arg_0-Arg_3])+max([2, 2+1+3*Arg_0+max([-3*Arg_3, -3*max([Arg_3, Arg_3+2*max([0, 1+Arg_0-Arg_3])])])])+max([0, 1+Arg_0-Arg_1])+max([0, -(Arg_3)+max([Arg_1, Arg_1+2*max([0, 1+Arg_0-Arg_1])])])+max([0, 1+Arg_0-Arg_1])+max([0, 1+Arg_0-Arg_3])+max([0, Arg_0-Arg_3])+max([0, -(Arg_7)+max([Arg_1, Arg_1+2*max([0, 1+Arg_0-Arg_1])])])+max([0, Arg_0-Arg_3])+max([0, 1+2*Arg_0+max([-2*Arg_3, -2*max([Arg_3, Arg_3+2*max([0, 1+Arg_0-Arg_3])])])])+max([0, -(Arg_3)+max([Arg_1, Arg_1+2*max([0, 1+Arg_0-Arg_1])])])+max([0, 1+Arg_0-Arg_1])+max([0, -(Arg_3)+max([Arg_1, Arg_1+2*max([0, 1+Arg_0-Arg_1])])])+max([0, 1+Arg_0-Arg_3])+max([0, max([5*Arg_1, 5*max([Arg_1, Arg_1+2*max([0, 1+Arg_0-Arg_1])])])+max([-5*Arg_3, -5*max([Arg_3, Arg_3+2*max([0, 1+Arg_0-Arg_3])])])])+max([0, 1+Arg_0-Arg_3]) {O(n)}) 39.21/20.30 39.21/20.30 39.21/20.30 39.21/20.30 Initial Complexity Problem: 39.21/20.30 39.21/20.30 Start: f2 39.21/20.30 39.21/20.30 Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3, Arg_4, Arg_5, Arg_6, Arg_7, Arg_8, Arg_9, Arg_10 39.21/20.30 39.21/20.30 Temp_Vars: L 39.21/20.30 39.21/20.30 Locations: f1, f2, f23, f26, f40, f5, f59, f69, f71, f74, f9 39.21/20.30 39.21/20.30 Transitions: 39.21/20.30 39.21/20.30 f2(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f5(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|: 39.21/20.30 39.21/20.30 f23(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f1(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_0 <= Arg_1 && 1+Arg_0 <= Arg_3 39.21/20.30 39.21/20.30 f23(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f26(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_0 <= Arg_1 && Arg_3 <= Arg_0 39.21/20.30 39.21/20.30 f26(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f40(Arg_0,Arg_1,0,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_3 <= Arg_1 && Arg_3 <= Arg_0 && 1+Arg_0 <= Arg_1 && Arg_3 <= Arg_1 39.21/20.30 39.21/20.30 f40(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f59(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_3 <= Arg_1 && Arg_3 <= Arg_0 && Arg_2 <= 0 && 0 <= Arg_2 && 1+Arg_0 <= Arg_1 && 1+Arg_0 <= Arg_1 && Arg_3+1 <= Arg_10 39.21/20.30 39.21/20.30 f40(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f59(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_3 <= Arg_1 && Arg_3 <= Arg_0 && Arg_2 <= 0 && 0 <= Arg_2 && 1+Arg_0 <= Arg_1 && 1+Arg_0 <= Arg_1 && 1+Arg_10 <= Arg_3 39.21/20.30 39.21/20.30 f40(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f69(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_3):|:1+Arg_3 <= Arg_1 && Arg_3 <= Arg_0 && Arg_2 <= 0 && 0 <= Arg_2 && 1+Arg_0 <= Arg_1 && 1+Arg_0 <= Arg_1 && Arg_3 <= Arg_10 && Arg_10 <= Arg_3 39.21/20.30 39.21/20.30 f5(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f23(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_0 <= Arg_1 39.21/20.30 39.21/20.30 f5(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f9(Arg_0,Arg_1,0,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:Arg_1 <= Arg_0 39.21/20.30 39.21/20.30 f59(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f59(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7+1,L,Arg_9,Arg_10):|:1+Arg_3 <= Arg_1 && Arg_3 <= Arg_0 && Arg_2 <= 0 && 0 <= Arg_2 && 1+Arg_0 <= Arg_1 && Arg_7 <= Arg_0 39.21/20.30 39.21/20.30 f59(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f69(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_3 <= Arg_1 && Arg_3 <= Arg_0 && Arg_2 <= 0 && 0 <= Arg_2 && 1+Arg_0 <= Arg_1 && 1+Arg_0 <= Arg_7 39.21/20.30 39.21/20.30 f69(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f71(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_3 <= Arg_1 && Arg_3 <= Arg_0 && Arg_2 <= 0 && 0 <= Arg_2 && 1+Arg_0 <= Arg_1 && L+1 <= 0 39.21/20.30 39.21/20.30 f69(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f71(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_3 <= Arg_1 && Arg_3 <= Arg_0 && Arg_2 <= 0 && 0 <= Arg_2 && 1+Arg_0 <= Arg_1 && 1 <= L 39.21/20.30 39.21/20.30 f69(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10) -> f71(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10):|:1+Arg_3 <= Arg_1 && Arg_3 <= Arg_0 && Arg_2 <= 0 && 0 <= Arg_2 && 1+Arg_0 <= Arg_1
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