details

property	value
status	complete
benchmark	fun6.koat
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n109.star.cs.uiowa.edu
space	T2

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	23.1791830063 seconds
cpu usage	50.729004481
max memory	5.57092864E8

stage attributes

key	value
output-size	239645
starexec-result	WORST_CASE(NON_POLY, ?)

output

/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(NON_POLY, ?) 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(INF, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 21.5 s] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f30(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> 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, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: TRUE 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f2(K1, 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, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: TRUE 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f3(A, 0, 0, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: TRUE f3(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f3(A, B + 1, 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, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: A >= B + 1 f3(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f4(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, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: B >= A f4(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f5(A, B, C, 0, C, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f5(A, B, C, D + 1, E - 1, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: E >= 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f5(A, B, C, D, E, K1, L1, M1, N1, O1, P1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f1(A, B, C, D, E, K1, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: I >= H && F >= 0 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f16(A, B, C, D, E, 1 + F, G, H, 1 + I, J, K, M, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: 0 >= E && F >= 0 f3(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f2(A, B, C, D, E, K1, G, H, I, J, K, L, O, O, O, 0, 0, O, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: L1 >= 1 && F >= 1 && N >= 0 && N <= 0 f3(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f25(A, B, C, D, E, K1, G, H, I, J, K, L, M, N, O, N, 0, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: F >= 1 && N >= 1 && K1 >= 1 f3(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f25(A, B, C, D, E, K1, G, H, I, J, K, L, M, N, O, N, 0, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: F >= 1 && 0 >= N + 1 && K1 >= 1 f4(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f17(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, J, 0, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: J >= 1 f4(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f17(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, J, 0, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: 0 >= J + 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f18(A, B, C, D, E, K1, G, H, I, 0, K, L, M, N, O, P, Q, R, 0, 0, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: K1 >= 0 && F >= 0 && J >= 0 && J <= 0 f12(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f16(A, B, C, D, E, I, G, H, 1 + I, J, K, M, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: TRUE 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f22(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, M, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: TRUE f4(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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f21(A, B, C, D, E, F, G, H, I, 0, K, L, K1, N, O, P, Q, R, 0, 0, 0, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: J >= 0 && J <= 0 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f3(A, B, C, D, E, K1, N1, O1, P1, U1, K, M1, M, R1, T1, P, Q, R, L1, 0, U, J, S1, V1, W1, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: F >= 0 && J >= 1 && Q1 >= 0 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f3(A, B, C, D, E, K1, N1, O1, P1, U1, K, M1, M, R1, T1, P, Q, R, L1, 0, U, J, S1, V1, W1, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: F >= 0 && 0 >= J + 1 && Q1 >= 0 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f4(A, B, C, D, E, F, K1, L1, M1, N1, K, 0, M, N, O, P, Q, R, S, T, U, V, W, X, Y, O1, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1)) :|: 0 >= P1 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f16(A, B, C, D, E, 1 + K1, M1, N1, 1 + O1, J, K, L1, L1, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, L1, L1, L1, P1, R1, S1, T1, U1, I1, J1)) :|: F >= 0 && V1 >= 0 && H >= 1 + I && K1 >= 0 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, B1, C1, D1, E1, F1, G1, H1, I1, J1) -> Com_1(f16(A, B, C, D, E, K1, M1, N1, 1 + K1, J, K, L1, L1, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, L1, L1, L1, O1, P1, R1, G1, H1, S1, T1)) :|: U1 >= 1 The start-symbols are:[f30_36] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f30 0: f30 -> f1 : [], cost: 1 1: f1 -> f2 : A'=free, [], cost: 1 7: f1 -> f5 : F'=free_2, G'=free_5, H'=free_3, Q'=free_1, J'=free_6, K'=free_4, [], cost: 1 2: f2 -> f3 : B'=0, C'=0, [], cost: 1 17: f2 -> f22 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=M, G1'=N, H'=O, H1'=P, Q'=Q_1, Q1'=R, J'=S, J1'=M, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, Q_1'=G1, Q1_1'=H1, R'=Q1, R1'=J1, [], cost: 1 3: f3 -> f3 : B'=1+B, C'=1+C, [ A>=1+B ], cost: 1 4: f3 -> f4 : [ B>=A ], cost: 1 10: f3 -> f2 : F'=free_8, M'=O, N'=O, P'=0, Q_1'=0, R'=O, [ free_9>=1 && F>=1 && N==0 ], cost: 1 11: f3 -> f25 : A1'=B, B'=C, B1'=D, C'=E, C1'=free_10, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=M, G1'=N, H'=O, H1'=N, Q'=0, Q1'=R, J'=S, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, Q_1'=G1, Q1_1'=H1, R'=Q1, R1'=J1, [ F>=1 && N>=1 && free_10>=1 ], cost: 1 12: f3 -> f25 : A1'=B, B'=C, B1'=D, C'=E, C1'=free_11, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=M, G1'=N, H'=O, H1'=N, Q'=0, Q1'=R, J'=S, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, Q_1'=G1, Q1_1'=H1, R'=Q1, R1'=J1, [ F>=1 && 0>=1+N && free_11>=1 ], cost: 1 5: f4 -> f5 : D'=0, E'=C, [], cost: 1 13: f4 -> f17 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=M, G1'=N, H'=O, H1'=P, Q'=Q_1, Q1'=R, J1'=0, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, Q_1'=G1, Q1_1'=H1, R'=Q1, R1'=J1, [ J>=1 ], cost: 1 14: f4 -> f17 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=M, G1'=N, H'=O, H1'=P, Q'=Q_1, Q1'=R, J1'=0, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, Q_1'=G1, Q1_1'=H1, R'=Q1, R1'=J1, [ 0>=1+J ], cost: 1 18: f4 -> f21 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=0, F'=K, F1'=L, G'=free_13, G1'=N, H'=O, H1'=P, Q'=Q_1, Q1'=R, J'=0, J1'=0, K'=0, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, Q_1'=G1, Q1_1'=H1, R'=Q1, R1'=J1, [ J==0 ], cost: 1 6: f5 -> f5 : D'=1+D, E'=-1+E, [ E>=1 ], cost: 1 9: f5 -> f16 : F'=1+F, Q'=1+Q, L'=M, [ 0>=E && F>=0 ], cost: 1 15: f5 -> f18 : A1'=B, B'=C, B1'=D, C'=E, C1'=free_12, D'=G, D1'=H, E'=Q, E1'=0, F'=K, F1'=L, G'=M, G1'=N, H'=O, H1'=P, Q'=Q_1, Q1'=R, J'=0, J1'=0, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, Q_1'=G1, Q1_1'=H1, R'=Q1, R1'=J1, [ free_12>=0 && F>=0 && J==0 ], cost: 1 19: f5 -> f3 : F'=free_16, G'=free_23, H'=free_19, Q'=free_14, J'=free_25, L'=free_20, N'=free_22, O'=free_18, S'=free_26, T'=0, V'=J, W'=free_21, X'=free_17, Y'=free_24, [ F>=0 && J>=1 && free_15>=0 ], cost: 1 popout

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

job log

popout

actions

all output return to Compl Integ Trans Syste 26843