Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Complexity_ITS 2019-03-21 04.46 pair #429990070
details
property
value
status
complete
benchmark
hongyi1.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n145.star.cs.uiowa.edu
space
T2
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
32.3095 seconds
cpu usage
75.9166
user time
74.4141
system time
1.50246
max virtual memory
1.9202936E7
max residence set size
544256.0
stage attributes
key
value
starexec-result
WORST_CASE(Omega(n^1), O(n^1))
output
75.73/32.25 WORST_CASE(Omega(n^1), O(n^1)) 75.73/32.27 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 75.73/32.27 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 75.73/32.27 75.73/32.27 75.73/32.27 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). 75.73/32.27 75.73/32.27 (0) CpxIntTrs 75.73/32.27 (1) Koat Proof [FINISHED, 30.5 s] 75.73/32.27 (2) BOUNDS(1, n^1) 75.73/32.27 (3) Loat Proof [FINISHED, 10.4 s] 75.73/32.27 (4) BOUNDS(n^1, INF) 75.73/32.27 75.73/32.27 75.73/32.27 ---------------------------------------- 75.73/32.27 75.73/32.27 (0) 75.73/32.27 Obligation: 75.73/32.27 Complexity Int TRS consisting of the following rules: 75.73/32.27 f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: A >= 1 75.73/32.27 f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: 0 >= B 75.73/32.27 f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f10(A, B, C, D, 0, 1, 0, H, I, J, K, L, M, N, O, P, Q)) :|: C >= 0 && D >= 1 75.73/32.27 f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f14(A, B, C, D, E, F, G, 1, I, J, K, L, M, N, O, P, Q)) :|: D >= G + 1 && 0 >= G 75.73/32.27 f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f14(A, B, C, D, E, F, G, 0, I, J, K, L, M, N, O, P, Q)) :|: D >= G + 1 && G >= 1 75.73/32.27 f14(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f23(A, B, C, D, E, F, G, H, I, 1, L, L, M, N, O, P, Q)) :|: I >= 0 && G + 1 >= D && 1 >= I 75.73/32.27 f14(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f23(A, B, C, D, E, F, G, H, I, 0, L, L, M, N, O, P, Q)) :|: I >= 0 && D >= 2 + G && 1 >= I 75.73/32.27 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f27(A, B, C, D, E + 1, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: I >= 1 && 0 >= C && 0 >= E 75.73/32.27 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f27(A, B, C, D, E + 1, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: I >= 1 && 0 >= C && E >= 1 && E <= 1 75.73/32.27 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f27(A, B, C, D, 0, F + 1, G, H, I, J, K, L, M, N, O, P, Q)) :|: E >= 2 && C >= 0 && C <= 0 75.73/32.27 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f27(A, B, C - 1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: C >= 1 75.73/32.27 f27(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f42(H, J, C, D, E, F, G, H, I, J, K, L, 1, K, O, P, Q)) :|: M >= 1 && I >= 1 75.73/32.27 f27(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f42(H, J, C, D, E, F, G, H, I, J, K, L, 1, K, K, P, Q)) :|: 0 >= M && I >= 1 75.73/32.27 f42(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f44(A, B, C, D, E, F, G, H, I, J, K, L, M, N, N, P, Q)) :|: 0 >= A + 1 && N >= O && N <= O 75.73/32.27 f42(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f44(A, B, C, D, E, F, G, H, I, J, K, L, M, N, N, P, Q)) :|: A >= 1 && N >= O && N <= O 75.73/32.27 f42(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f48(0, B, C, D, E, F, G, H, I, J, K, L, M, N, N, P, Q)) :|: A >= 0 && A <= 0 && N >= O && N <= O 75.73/32.27 f44(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f46(A, 0, C, D, E, F, G, H, I, J, K, L, M, N, O, 1, Q)) :|: B >= 0 && B <= 0 75.73/32.27 f44(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: 0 >= B + 1 75.73/32.27 f44(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: B >= 1 75.73/32.27 f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, 2, Q)) :|: 0 >= B && 0 >= A 75.73/32.27 f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: B >= 1 && 0 >= A 75.73/32.27 f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, 3, Q)) :|: B >= 1 75.73/32.27 f42(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: Q >= 0 && N >= O + 1 && 1 >= Q 75.73/32.27 f42(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: Q >= 0 && O >= 1 + N && 1 >= Q 75.73/32.27 f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, 0, P, Q)) :|: Q >= 0 && O >= 1 && 1 >= Q 75.73/32.27 f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, 1, P, Q)) :|: Q >= 0 && 0 >= O && 1 >= Q 75.73/32.27 f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f63(A, B, C, D, E + 1, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: Q >= 1 && 0 >= C && 0 >= E 75.73/32.27 f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f63(A, B, C, D, E + 1, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: Q >= 1 && 0 >= C && E >= 1 && E <= 1 75.73/32.27 f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f63(A, B, C, D, 0, F + 1, G, H, I, J, K, L, M, N, O, P, Q)) :|: E >= 2 && C >= 0 && C <= 0 75.73/32.27 f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f63(A, B, C - 1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: C >= 1 75.73/32.27 f63(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: I >= 0 && 1 >= I && 0 >= Q && D >= F 75.73/32.27 f63(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: I >= 0 && 1 >= I && Q >= 2 && D >= F 75.73/32.27 f27(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: D >= F && I >= 0 && I <= 0 75.73/32.27 f63(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f10(A, B, C, D, E, F, G + 1, H, I, J, K, 0, M, N, O, P, 1)) :|: L >= 1 && D >= F && Q >= 1 && Q <= 1 75.73/32.27 f63(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f10(A, B, C, D, E, F, G + 1, H, I, J, K, 1, M, N, O, P, 1)) :|: 0 >= L && D >= F && Q >= 1 && Q <= 1 75.73/32.27 f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q)) :|: G >= D 75.73/32.27 75.73/32.27 The start-symbols are:[f2_17] 75.73/32.27 75.73/32.27 75.73/32.27 ---------------------------------------- 75.73/32.27 75.73/32.27 (1) Koat Proof (FINISHED) 75.73/32.27 YES(?, 190*ar_2 + 413*ar_3 + 13) 75.73/32.27 75.73/32.27 75.73/32.27 75.73/32.27 Initial complexity problem: 75.73/32.27 75.73/32.27 1: T: 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f48(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_0 >= 1 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f46(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ 0 >= ar_1 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f2(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f10(ar_0, ar_1, ar_2, ar_3, 0, 1, 0, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_2 >= 0 /\ ar_3 >= 1 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f10(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f14(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, 1, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_3 >= ar_6 + 1 /\ 0 >= ar_6 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f10(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f14(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, 0, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_3 >= ar_6 + 1 /\ ar_6 >= 1 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f14(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f23(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, 1, ar_11, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_8 >= 0 /\ ar_6 + 1 >= ar_3 /\ 1 >= ar_8 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f14(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f23(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, 0, ar_11, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_8 >= 0 /\ ar_3 >= ar_6 + 2 /\ 1 >= ar_8 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f23(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f27(ar_0, ar_1, ar_2, ar_3, ar_4 + 1, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_8 >= 1 /\ 0 >= ar_2 /\ 0 >= ar_4 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f23(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f27(ar_0, ar_1, ar_2, ar_3, ar_4 + 1, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_8 >= 1 /\ 0 >= ar_2 /\ ar_4 = 1 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f23(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f27(ar_0, ar_1, ar_2, ar_3, 0, ar_5 + 1, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_4 >= 2 /\ ar_2 = 0 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f23(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f27(ar_0, ar_1, ar_2 - 1, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16)) [ ar_2 >= 1 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f27(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f42(ar_7, ar_9, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, 1, ar_10, ar_14, ar_15, ar_16)) [ ar_12 >= 1 /\ ar_8 >= 1 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f27(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f42(ar_7, ar_9, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, 1, ar_10, ar_10, ar_15, ar_16)) [ 0 >= ar_12 /\ ar_8 >= 1 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f42(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f44(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_13, ar_15, ar_16)) [ 0 >= ar_0 + 1 /\ ar_13 = ar_14 ] 75.73/32.27 75.73/32.27 (Comp: ?, Cost: 1) f42(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16) -> Com_1(f44(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_13, ar_15, ar_16)) [ ar_0 >= 1 /\ ar_13 = ar_14 ] 75.73/32.27
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