details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	15.6425189972 seconds
cpu usage	23.267175766
max memory	6.71215616E8

stage attributes

key	value
output-size	268898
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, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 2894 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 13.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(f13(A, 0, 0, 2 * A, 4 * A, 4 * A + 3, 4 * A + 4, A, C1, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: 1 >= A * B1 && A * B1 + B1 >= 2 && C1 >= B1 && 1 >= A * D1 && A * D1 + D1 >= 2 && D1 >= C1 f13(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(f13(A, B, C, D, E, F, G, H, I, J + 1, 1, 0, 0, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: D >= J f13(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(f13(A, B + 1 - 2 * C1 + C1 * C1, C, D, E, F, G, H, I, J + 1, C1, 1 - C1, 1 - 2 * C1 + C1 * C1, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: C1 >= 2 && D >= J f13(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(f13(A, B + 1 - 2 * C1 + C1 * C1, C, D, E, F, G, H, I, J + 1, C1, 1 - C1, 1 - 2 * C1 + C1 * C1, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: 0 >= C1 && D >= J f24(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(f24(A, B, C, D, E, F, G, H, I, J + 1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= J 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(f31(A, B, C, D, E, F, G, H, I, J + 1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= J f37(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)) :|: N >= O 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(f44(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 >= P + 1 && 0 >= Q 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(f44(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)) :|: P >= 1 && 0 >= Q f44(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(f44(A, B, C, D, E, F, G, H, I, J + 1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= J 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(f50(A, B, C, D, E, F, G, H, I, J + 1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= J f57(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(f57(A, B, C, D, E, F, G, H, I, J + 1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= J 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(f64(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, 0, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: 0 >= Q && P >= 0 && P <= 0 f64(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(f64(A, B, C, D, E, F, G, H, I, J + 2, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: E >= J f71(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(f71(A, B, C, D, E, F, G, H, I, J + 1, K, L, M, N, O, P, Q, 2 * J, C1, 1 - C1, U, V, W, X, Y, Z, A1)) :|: D >= J f86(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(f91(A, B, C, D, E, F, G, H, I, J, K, 0, M, N, O, P, Q, R, S, T, 0, V, W, X, Y, Z, A1)) :|: L >= 0 && L <= 0 f86(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(f91(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, L * L, V, W, X, Y, Z, A1)) :|: 0 >= L + 1 f86(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(f91(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, L * L, V, W, X, Y, Z, A1)) :|: L >= 1 f91(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(f99(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, 2 * J, S, T, U, 0, W, X, Y, Z, A1)) :|: A >= J f91(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(f99(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, 2 * J, S, T, U, B1 * B1, W, X, Y, Z, A1)) :|: 0 >= B1 + 1 && A >= J f91(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(f99(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, 2 * J, S, T, U, B1 * B1, W, X, Y, Z, A1)) :|: B1 >= 1 && A >= J f99(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(f103(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, R, S, T, U, V, 0, X, Y, Z, A1)) :|: L >= 0 && L <= 0 f99(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(f103(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, R, S, T, U, V, L * L, X, Y, Z, A1)) :|: 0 >= L + 1 f99(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(f103(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, R, S, T, U, V, L * L, X, Y, Z, A1)) :|: L >= 1 f103(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(f107(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, R, S, T, U, V, W, 0, Y, Z, A1)) :|: L >= 0 && L <= 0 f103(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(f107(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, R, S, T, U, V, W, L * L, Y, Z, A1)) :|: 0 >= L + 1 f103(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(f107(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, R, S, T, U, V, W, L * L, Y, Z, A1)) :|: L >= 1 f107(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(f91(A, B, C, D, E, F, G, H, I, J + 1, K, 0, M, N, O, P, Q, R, S, T, U, V, W, X, 0, Z, A1)) :|: L >= 0 && L <= 0 f107(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(f91(A, B, C, D, E, F, G, H, I, J + 1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, L * L, Z, A1)) :|: 0 >= L + 1 f107(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(f91(A, B, C, D, E, F, G, H, I, J + 1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, L * L, Z, A1)) :|: L >= 1 f118(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(f118(A, B, C, D, E, F, G, H, I, J + 1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= J f118(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)) :|: J >= 1 + A f91(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(f37(A, B, C + B, D, E, F, G, H, I, J, K, L, M, N, O + 1, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: J >= 1 + A f71(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(f86(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, R, S, T, U, V, W, X, Y, 0, A1)) :|: J >= 1 + D f71(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(f86(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, R, S, T, U, V, W, X, Y, B1 * B1, A1)) :|: 0 >= B1 + 1 && J >= 1 + D f71(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(f86(A, B, C, D, E, F, G, H, I, J, K, C1, M, N, O, P, Q, R, S, T, U, V, W, X, Y, B1 * B1, A1)) :|: B1 >= 1 && J >= 1 + D f64(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 + 1, R, S, T, U, V, W, X, Y, Z, A1)) :|: J >= 1 + E f57(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 + 1, R, S, T, U, V, W, X, Y, Z, A1)) :|: J >= 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(f57(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, Q + D)) :|: J >= 1 + A f44(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, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: J >= 1 + 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(f71(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 >= 1 f37(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(f118(A, B, C * E, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: O >= 1 + N 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(f37(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)) :|: J >= 1 + A f24(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, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: 0 >= P + 1 && J >= 1 + A f24(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, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: P >= 1 && J >= 1 + A f24(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(f37(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, 0, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: J >= 1 + A && P >= 0 && P <= 0 f13(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(f24(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)) :|: J >= 1 + D The start-symbols are:[f2_27] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 375*ar_0 + 278*ar_9 + 23*ar_13 + 23*ar_14 + 76*ar_16 + 413) Initial complexity problem: 1: T: (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, ar_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26) -> Com_1(f13(ar_0, 0, 0, 2*ar_0, 4*ar_0, 4*ar_0 + 3, 4*ar_0 + 4, ar_0, c1, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16, ar_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26)) [ 1 >= ar_0*b1 /\ ar_0*b1 + b1 >= 2 /\ c1 >= b1 /\ 1 >= ar_0*d1 /\ ar_0*d1 + d1 >= 2 /\ d1 >= c1 ] (Comp: ?, Cost: 1) f13(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_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26) -> Com_1(f13(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9 + 1, 1, 0, 0, ar_13, ar_14, ar_15, ar_16, ar_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26)) [ ar_3 >= ar_9 ] (Comp: ?, Cost: 1) f13(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_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26) -> Com_1(f13(ar_0, ar_1 - 2*c1 + c1^2 + 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9 + 1, c1, -c1 + 1, -2*c1 + c1^2 + 1, ar_13, ar_14, ar_15, ar_16, ar_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26)) [ c1 >= 2 /\ ar_3 >= ar_9 ] (Comp: ?, Cost: 1) f13(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_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26) -> Com_1(f13(ar_0, ar_1 - 2*c1 + c1^2 + 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9 + 1, c1, -c1 + 1, -2*c1 + c1^2 + 1, ar_13, ar_14, ar_15, ar_16, ar_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26)) [ 0 >= c1 /\ ar_3 >= ar_9 ] (Comp: ?, Cost: 1) f24(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_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26) -> Com_1(f24(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9 + 1, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16, ar_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26)) [ ar_0 >= ar_9 ] (Comp: ?, Cost: 1) f31(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_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26) -> Com_1(f31(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9 + 1, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15, ar_16, ar_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26)) [ ar_0 >= ar_9 ] (Comp: ?, Cost: 1) f37(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_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26) -> Com_1(f40(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_17, ar_18, ar_19, ar_20, ar_21, ar_22, ar_23, ar_24, ar_25, ar_26)) [ ar_13 >= ar_14 ] popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to Compl Integ Trans Syste 26843