Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Compl Integ Trans Syste 26843 pair #381744420
details
property
value
status
complete
benchmark
jacobi.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n030.star.cs.uiowa.edu
space
T2
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
148.500261068 seconds
cpu usage
161.774751489
max memory
7.07039232E8
stage attributes
key
value
output-size
165964
starexec-result
WORST_CASE(Omega(n^1), O(n^1))
output
/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/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, max(5 + Arg_0 + -1 * Arg_2, 4) + max(2, 4 + 2 * Arg_0 + -2 * Arg_2) + nat(1 + Arg_0 + -1 * Arg_3)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 6518 ms] (2) BOUNDS(1, max(5 + Arg_0 + -1 * Arg_2, 4) + max(2, 4 + 2 * Arg_0 + -2 * Arg_2) + nat(1 + Arg_0 + -1 * Arg_3)) (3) Loat Proof [FINISHED, 147.0 s] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f0(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(f16(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 f16(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(f18(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 f18(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(f18(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 f26(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(f26(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 f35(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(f38(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 f38(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(f40(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 f40(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(f40(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 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(f56(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 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(f56(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 f56(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(f58(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 f74(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(f58(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 f58(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(f58(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 f58(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(f74(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 f58(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(f74(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 f58(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(f74(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 f58(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(f74(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 f58(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(f74(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 f74(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(f85(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 f74(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(f85(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 f85(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(f96(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 f74(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(f96(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 f85(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(f96(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 f96(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(f96(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 f104(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(f104(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 f112(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(f112(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 f120(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(f120(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(f35(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 f120(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(f58(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 f112(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(f120(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 f104(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(f112(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 f96(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(f104(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 f58(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(f56(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 f56(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 f40(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(f38(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 f38(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)) :|: B >= A && 0 >= F + 1 f38(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)) :|: B >= A && F >= 1 f38(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(f52(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 f35(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(f52(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 f26(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(f35(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 f18(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(f16(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 f16(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(f26(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:[f0_27] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, 4+max([0, 1+Arg_0-Arg_2])+max([2, 2+2+2*Arg_0+-2*Arg_2])+max([0, 1+Arg_0-Arg_3]) {O(n)}) Initial Complexity Problem: Start: f0 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: f0, f16, f18, f26, f35, f38, f52 Transitions: f0(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) -> f16(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):|: f16(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) -> f18(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):|:Arg_2 <= Arg_0 f16(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) -> f26(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 f18(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) -> f16(Arg_0,Arg_1,Arg_2+1,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):|:Arg_2 <= Arg_0 && 1+Arg_0 <= Arg_3 f18(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) -> f18(Arg_0,Arg_1,Arg_2,Arg_3+1,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):|:Arg_2 <= Arg_0 && Arg_3 <= Arg_0
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Compl Integ Trans Syste 26843