Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Compl Integ Trans Syste 26843 pair #381745134
details
property
value
status
complete
benchmark
jacobi.c.i.jacobi.pl.t2.nor.t2.rlgfixed.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n028.star.cs.uiowa.edu
space
T2
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
147.068186998 seconds
cpu usage
160.350787191
max memory
7.07465216E8
stage attributes
key
value
output-size
165249
starexec-result
WORST_CASE(Omega(n^1), O(n^1))
output
/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.koat # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, nat(1 + Arg_0 + -1 * Arg_2) + max(6, 7 + Arg_0 + -1 * Arg_2) + nat(1 + Arg_0 + -1 * Arg_3)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 6356 ms] (2) BOUNDS(1, nat(1 + Arg_0 + -1 * Arg_2) + max(6, 7 + Arg_0 + -1 * Arg_2) + nat(1 + Arg_0 + -1 * Arg_3)) (3) Loat Proof [FINISHED, 145.7 s] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: TRUE f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f8(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= B f8(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f8(A, B, C + 1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= C f17(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f17(A, B + 1, C, B1, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= B f27(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f31(A, B, C, D, E, 0, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: 50 >= E f31(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f34(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= 1 + B f34(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f34(A, B, C + 1, D, E, F + B1, B1, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= C f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f50(A, B, C, D, E, F, G, B1, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: 3 >= E f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f50(A, B, C, D, E, F, G, 0, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: E >= 4 f50(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= 1 + B f69(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f53(A, B, C + 1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: H >= I f53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f53(A, B, C + 1, D, E, F, G, H, I, B1, C1, D1, D1 + C1, E1, E1 + C1, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= C && E >= 5 f53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f69(A, B, C, D, E, F, G, H, D1, B1, C1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= C && 4 >= E f53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f69(A, B, C, D, E, F, G, H, G1, B1, C1, D1, D1 + C1, E1, F1, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: E >= 5 && A >= C && F1 >= E1 + C1 + 1 f53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f69(A, B, C, D, E, F, G, H, G1, B1, C1, D1, D1 + C1, E1, F1, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: E >= 5 && A >= C && E1 + C1 >= 1 + F1 f53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f69(A, B, C, D, E, F, G, H, F1, B1, C1, D1, E1, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: E >= 5 && A >= C && E1 >= D1 + C1 + 1 f53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f69(A, B, C, D, E, F, G, H, F1, B1, C1, D1, E1, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: E >= 5 && A >= C && D1 + C1 >= 1 + E1 f69(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f80(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, B1 - C1, D1, E1, F1, G1, H1, I1, W, X, Y, Z, A1)) :|: I >= 1 + H && E1 >= D1 + K + 1 f69(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f80(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, B1 - C1, D1, E1, F1, G1, H1, I1, W, X, Y, Z, A1)) :|: I >= 1 + H && D1 + K >= 1 + E1 f80(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f92(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, B1, Q, R, S, T, U, V, C1, D1, E1, F1, A1)) :|: T >= 0 f69(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f92(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, B1, C1, C1 + K, D1, T, U, V, E1, F1, G1, H1, A1)) :|: I >= 1 + H f80(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f92(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, B1, Q, R, -(S), T, U, V, C1, D1, E1, F1, A1)) :|: 0 >= T + 1 f92(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f92(A, B, C, D, E, F, G, H, I, J, B1, L, M, N, O, C1, Q, R, S, T, U, V, W, X, Y, Z, A1 + 1)) :|: B >= 1 + A1 f101(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f101(A, B, C, D, E, F, G, H, I, J, B1, L, M, N, O, C1, Q, R, S, T, U, V, W, X, Y, Z, A1 + 1)) :|: C >= 1 + A1 f110(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f110(A, B, C, D, E, F, G, H, I, J, B1, L, M, N, O, C1, Q, R, S, T, U, V, W, X, Y, Z, A1 + 1)) :|: A >= A1 f119(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f119(A, B, C, D, E, F, G, H, I, J, B1, L, M, N, O, C1, Q, R, S, T, U, V, W, X, Y, Z, A1 + 1)) :|: A >= A1 f132(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f132(A, B + 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= B f132(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f27(A, B, C, D, E + 1, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: B >= 1 + A f119(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f53(A, B, C + 1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A1 >= 1 + A f110(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f119(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A1 >= 1 + A f101(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f110(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A1 >= C f92(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f101(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A1 >= B f53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f50(A, B + 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: C >= 1 + A f50(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f132(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: B >= A f34(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f31(A, B + 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: C >= 1 + A f31(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: B >= A && 0 >= F + 1 f31(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: B >= A && F >= 1 f31(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f1(A, B, C, D, E, 0, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: B >= A && F >= 0 && F <= 0 f27(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: E >= 51 f17(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f27(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: B >= 1 + A f8(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f5(A, B + 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: C >= 1 + A f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f17(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: B >= 1 + A The start-symbols are:[f2_27] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, max([0, 1+Arg_0-Arg_2])+max([6, 7+Arg_0-Arg_2])+max([0, 1+Arg_0-Arg_3]) {O(n)}) Initial Complexity Problem: Start: f2 Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3, Arg_4, Arg_5, Arg_6, Arg_7, Arg_8, Arg_9, Arg_10, Arg_11, Arg_12, Arg_13, Arg_14, Arg_15, Arg_16, Arg_17, Arg_18, Arg_19, Arg_20, Arg_21, Arg_22, Arg_23, Arg_24, Arg_25, Arg_26 Temp_Vars: Locations: f1, f17, f2, f27, f31, f5, f8 Transitions: f17(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26) -> f27(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26):|:1+Arg_0 <= Arg_2 && 1+Arg_0 <= Arg_2 f2(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26) -> f5(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26):|: f27(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26) -> f1(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26):|:1+Arg_0 <= Arg_2 && 51 <= Arg_5 f27(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26) -> f31(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,0,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26):|:1+Arg_0 <= Arg_2 && Arg_5 <= 50 f31(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26) -> f1(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,0,Arg_7,Arg_8,Arg_9,Arg_10,Arg_11,Arg_12,Arg_13,Arg_14,Arg_15,Arg_16,Arg_17,Arg_18,Arg_19,Arg_20,Arg_21,Arg_22,Arg_23,Arg_24,Arg_25,Arg_26):|:Arg_6 <= 0 && Arg_5+Arg_6 <= 50 && 0 <= Arg_6 && Arg_5 <= 50+Arg_6 && Arg_5 <= 50 && 1+Arg_0 <= Arg_2 && Arg_0 <= Arg_2 && Arg_6 <= 0 && 0 <= Arg_6
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Compl Integ Trans Syste 26843