details

property	value
status	complete
benchmark	fourn.c.i.fourn.pl.t2.fixed.koat
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n091.star.cs.uiowa.edu
space	T2

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	35.5051 seconds
cpu usage	41.6575
user time	41.1613
system time	0.496151
max virtual memory	1.8476688E7
max residence set size	273064.0

stage attributes

key	value
starexec-result	WORST_CASE(Omega(n^1), O(n^1))

output

41.53/35.44 WORST_CASE(Omega(n^1), O(n^1)) 41.53/35.46 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 41.53/35.46 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 41.53/35.46 41.53/35.46 41.53/35.46 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(3, 4 + Arg_0 + -1 * Arg_2)). 41.53/35.46 41.53/35.46 (0) CpxIntTrs 41.53/35.46 (1) Koat2 Proof [FINISHED, 2837 ms] 41.53/35.46 (2) BOUNDS(1, max(3, 4 + Arg_0 + -1 * Arg_2)) 41.53/35.46 (3) Loat Proof [FINISHED, 33.6 s] 41.53/35.46 (4) BOUNDS(n^1, INF) 41.53/35.46 41.53/35.46 41.53/35.46 ---------------------------------------- 41.53/35.46 41.53/35.46 (0) 41.53/35.46 Obligation: 41.53/35.46 Complexity Int TRS consisting of the following rules: 41.53/35.46 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(f2(A, B + 1, C * B1, 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 41.53/35.46 f10(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(f19(A, B, C, D, B1, Q1, D1, G1, L1, 1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: D >= 2 * C1 && 3 * C1 >= D + 1 && C1 >= D1 && D >= 2 * E1 && 3 * E1 >= D + 1 && D1 >= E1 && D * B1 >= 2 * B1 * F1 && 2 * B1 * F1 + F1 >= D * B1 + 1 && F1 >= G1 && D * B1 >= 2 * B1 * H1 && 2 * B1 * H1 + H1 >= D * B1 + 1 && G1 >= H1 && C >= D * B1 * I1 && D * B1 * I1 + I1 >= C + 1 && C >= D * B1 * J1 && D * B1 * J1 + J1 >= C + 1 && D * B1 * I1 >= 2 * B1 * J1 * K1 && 2 * B1 * J1 * K1 + K1 >= D * B1 * I1 + 1 && K1 >= L1 && C >= D * B1 * M1 && D * B1 * M1 + M1 >= C + 1 && C >= D * B1 * N1 && D * B1 * N1 + N1 >= C + 1 && D * B1 * M1 >= 2 * B1 * N1 * O1 && 2 * B1 * N1 * O1 + O1 >= D * B1 * M1 + 1 && L1 >= O1 && B >= 1 && C >= D * B1 * P1 && D * B1 * P1 + P1 >= C + 1 && P1 >= Q1 && C >= D * B1 * R1 && D * B1 * R1 + R1 >= C + 1 && Q1 >= R1 41.53/35.46 f19(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(f23(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)) :|: H >= K && J >= K + 1 41.53/35.46 f23(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)) :|: K + G >= 2 + L 41.53/35.46 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, C, D, E, F, G, H, I, J, K, L, M + H, J + M - K, B1, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: I >= M 41.53/35.46 f19(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(f41(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, B1, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: K >= J && H >= 2 * Q1 && 3 * Q1 >= H + 1 && Q1 >= B1 && H >= 2 * D1 && 3 * D1 >= H + 1 && B1 >= D1 && H >= K 41.53/35.46 f41(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(f41(A, B, C, D, E, F, G, H, I, J - P, K, L, M, N, O, B1, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: J >= 1 + P && P >= 2 * Q1 && 3 * Q1 >= P + 1 && Q1 >= B1 && P >= 2 * D1 && 3 * D1 >= P + 1 && B1 >= D1 && P >= G 41.53/35.46 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(f63(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, 2 * Q, B1, Q1, D1, G1, 1, 0, Y, Z, A1)) :|: H >= Q + 1 41.53/35.46 f63(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(f66(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)) :|: Q >= M 41.53/35.46 f66(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, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: M + G >= 2 + L 41.53/35.46 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(f69(A, B, C, D, E, F, G, H, I, J, K + R, L, M, N, W * B1 - X * Q1, P, Q, R, S, T, U, V, W, X, K, K + Q, W * D1 + X * G1)) :|: I >= K 41.53/35.46 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(f66(A, B, C, D, E, F, G, H, I, J, K, L + 2, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: K >= 1 + I 41.53/35.46 f66(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(f63(A, B, C, D, E, F, G, H, I, J, K, L, M + G, N, O, P, Q, R, S, W, U, V, U * W - V * X + W, U * X + V * W + X, Y, Z, A1)) :|: L + 1 >= M + G 41.53/35.46 f63(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, R, R, S, T, U, V, W, X, Y, Z, A1)) :|: M >= 1 + Q 41.53/35.46 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(f10(A, B - 1, C, D * E, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: Q >= H 41.53/35.46 f41(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(f19(A, B, C, D, E, F, G, H, I, J + P, K + G, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: P >= G && P >= J 41.53/35.46 f41(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(f19(A, B, C, D, E, F, G, H, I, J + P, K + G, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: G >= P + 1 41.53/35.46 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(f23(A, B, C, D, E, F, G, H, I, J, K, L + 2, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: M >= 1 + I 41.53/35.46 f23(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(f41(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, B1, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: L + 1 >= K + G && H >= 2 * Q1 && 3 * Q1 >= H + 1 && Q1 >= B1 && H >= 2 * D1 && 3 * D1 >= H + 1 && B1 >= D1 41.53/35.46 f19(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, G, R, S, T, U, V, W, X, Y, Z, A1)) :|: K >= 1 + H 41.53/35.46 f10(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)) :|: 0 >= B 41.53/35.46 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(f10(A, B, C, 1, 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 41.53/35.46 start(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(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)) :|: TRUE 41.53/35.46 41.53/35.46 The start-symbols are:[start_27] 41.53/35.46 41.53/35.46 41.53/35.46 ---------------------------------------- 41.53/35.46 41.53/35.46 (1) Koat2 Proof (FINISHED) 41.53/35.46 YES( ?, max([3, 4+Arg_0-Arg_2]) {O(n)}) 41.53/35.46 41.53/35.46 41.53/35.46 41.53/35.46 Initial Complexity Problem: 41.53/35.46 41.53/35.46 Start: start 41.53/35.46 41.53/35.46 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 41.53/35.46 41.53/35.46 Temp_Vars: B1 41.53/35.46 41.53/35.46 Locations: f1, f10, f2, start 41.53/35.46 41.53/35.46 Transitions: 41.53/35.46 41.53/35.46 f10(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):|:Arg_4 <= 1 && 1 <= Arg_4 && 1+Arg_0 <= Arg_2 && Arg_2 <= 0 41.53/35.46 41.53/35.46 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) -> f10(Arg_0,Arg_1,Arg_2,Arg_3,1,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 41.53/35.46 41.53/35.46 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) -> f2(Arg_0,Arg_1,Arg_2+1,B1Arg_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 41.53/35.46 41.53/35.46 start(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) -> 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):|: 41.53/35.46 41.53/35.46 41.53/35.46 41.53/35.46 Timebounds: 41.53/35.46 41.53/35.46 Overall timebound: max([3, 4+Arg_0-Arg_2]) {O(n)} 41.53/35.46 41.53/35.46 20: f10->f1: 1 {O(1)} 41.53/35.46 41.53/35.46 0: f2->f2: max([0, 1+Arg_0-Arg_2]) {O(n)} 41.53/35.46 41.53/35.46 21: f2->f10: 1 {O(1)} 41.53/35.46 41.53/35.46 22: start->f2: 1 {O(1)} 41.53/35.46 41.53/35.46 41.53/35.46 41.53/35.46 Costbounds: 41.53/35.46 41.53/35.46 Overall costbound: max([3, 4+Arg_0-Arg_2]) {O(n)} 41.53/35.46 41.53/35.46 20: f10->f1: 1 {O(1)} 41.53/35.46 41.53/35.46 0: f2->f2: max([0, 1+Arg_0-Arg_2]) {O(n)} 41.53/35.46 41.53/35.46 21: f2->f10: 1 {O(1)} 41.53/35.46 41.53/35.46 22: start->f2: 1 {O(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