details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	3.09558 seconds
cpu usage	7.21294
user time	6.88944
system time	0.3235
max virtual memory	1.852586E7
max residence set size	239888.0

stage attributes

key	value
starexec-result	WORST_CASE(NON_POLY, ?)

output

6.97/3.06 WORST_CASE(NON_POLY, ?) 6.97/3.07 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 6.97/3.07 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.97/3.07 6.97/3.07 6.97/3.07 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 6.97/3.07 6.97/3.07 (0) CpxIntTrs 6.97/3.07 (1) Loat Proof [FINISHED, 1305 ms] 6.97/3.07 (2) BOUNDS(INF, INF) 6.97/3.07 6.97/3.07 6.97/3.07 ---------------------------------------- 6.97/3.07 6.97/3.07 (0) 6.97/3.07 Obligation: 6.97/3.07 Complexity Int TRS consisting of the following rules: 6.97/3.07 f33(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) -> Com_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)) :|: TRUE 6.97/3.07 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) -> Com_1(f25(G1, B, B, 0, 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)) :|: A >= 1 && B >= 1 && G1 >= 1 6.97/3.07 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) -> Com_1(f25(G1, B, B, 0, 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)) :|: A >= 1 && 0 >= B + 1 && G1 >= 1 6.97/3.07 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) -> Com_1(f16(J, B, C, D, G1, H1, H1, H1, H1, 1 + J, H1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: TRUE 6.97/3.07 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) -> Com_1(f16(1 + H1, B, C, D, E, G1, G1, G1, G1, 1 + J, G1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: H1 >= 0 && A >= 0 6.97/3.07 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) -> Com_1(f22(G1, L, 0, 0, E, F, G, H, L, J, K, L, L, L, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: H1 >= 1 && A >= 1 && B >= 0 && B <= 0 6.97/3.07 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) -> Com_1(f17(A, B, C, D, E, F, G, H, I, K1, 0, L, 0, N, G1, H1, J1, G1, L1, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: G1 >= 1 && 0 >= I1 6.97/3.07 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) -> Com_1(f17(A, B, C, D, E, F, G, H, I, K1, 0, L, 0, N, G1, H1, J1, G1, L1, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: 0 >= G1 + 1 && 0 >= I1 6.97/3.07 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) -> Com_1(f21(A, B, C, D, E, F, G, H, G1, K1, 0, L, 0, N, 0, H1, J1, 0, L1, 0, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: 0 >= I1 6.97/3.07 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) -> Com_1(f16(1 + H1, B, C, D, E, G1, G1, G1, G1, 1 + L1, G1, L, M, N, O, J1, K1, R, S, T, I1, N1, O1, P1, Q1, Z, A1, B1, C1, D1, E1, F1)) :|: A >= 0 && M1 >= 0 && Q >= 1 + J && H1 >= 0 6.97/3.07 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) -> Com_1(f18(G1, B, C, D, E, F, G, H, I, K1, K, L, 0, N, 0, H1, J1, 0, S, T, U, V, W, X, Y, L1, A1, B1, C1, D1, E1, F1)) :|: A >= 0 && I1 >= 0 && J >= Q && G1 >= 0 6.97/3.07 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) -> Com_1(f3(G1, N1, C, D, E, F, G, H, I, I1, J1, Q1, 0, N, H1, K1, L1, M1, S, T, U, V, W, X, Y, V1, O1, P1, T1, U1, E1, F1)) :|: A >= 0 && R1 >= 0 && S1 >= 0 && J >= Q && O1 >= 1 6.97/3.07 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) -> Com_1(f3(G1, N1, C, D, E, F, G, H, I, I1, J1, Q1, 0, N, H1, K1, L1, M1, S, T, U, V, W, X, Y, V1, O1, P1, T1, U1, E1, F1)) :|: A >= 0 && R1 >= 0 && S1 >= 0 && J >= Q && 0 >= O1 + 1 6.97/3.07 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) -> Com_1(f16(H1, B, C, D, E, G1, G1, G1, G1, 1 + H1, G1, L, M, N, O, J1, K1, R, S, T, L1, I1, N1, X, Y, Z, A1, B1, C1, D1, O1, P1)) :|: Q1 >= 1 6.97/3.07 6.97/3.07 The start-symbols are:[f33_32] 6.97/3.07 6.97/3.07 6.97/3.07 ---------------------------------------- 6.97/3.07 6.97/3.07 (1) Loat Proof (FINISHED) 6.97/3.07 6.97/3.07 6.97/3.07 ### Pre-processing the ITS problem ### 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Initial linear ITS problem 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 1: f3 -> f25 : A'=free, A1'=B, B1'=0, 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'=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, [ A>=1 && B>=1 && free>=1 ], cost: 1 6.97/3.07 6.97/3.07 2: f3 -> f25 : A'=free_1, A1'=B, B1'=0, 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'=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, [ A>=1 && 0>=1+B && free_1>=1 ], cost: 1 6.97/3.07 6.97/3.07 3: f3 -> f16 : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [], cost: 1 6.97/3.07 6.97/3.07 4: f3 -> f16 : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 ], cost: 1 6.97/3.07 6.97/3.07 5: f3 -> f22 : A'=free_7, A1'=L, B'=0, B1'=0, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=L, F'=K, F1'=L, G'=L, G1'=L, H'=O, H1'=P, Q'=Q_1, 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, [ free_6>=1 && A>=1 && B==0 ], cost: 1 6.97/3.07 6.97/3.07 6: f23 -> f17 : A1'=B, B'=C, B1'=D, C'=free_11, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=0, F1'=L, G'=0, G1'=N, H'=free_9, H1'=free_10, Q'=free_8, Q1'=free_9, J'=free_12, 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, [ free_9>=1 && 0>=free_13 ], cost: 1 6.97/3.07 6.97/3.07 7: f23 -> f17 : A1'=B, B'=C, B1'=D, C'=free_17, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=0, F1'=L, G'=0, G1'=N, H'=free_15, H1'=free_16, Q'=free_14, Q1'=free_15, J'=free_18, 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, [ 0>=1+free_15 && 0>=free_19 ], cost: 1 6.97/3.07 6.97/3.07 8: f23 -> f21 : A1'=B, B'=C, B1'=D, C'=free_21, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_23, F'=0, F1'=L, G'=0, G1'=N, H'=0, H1'=free_22, Q'=free_20, Q1'=0, J'=free_24, 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, [ 0>=free_25 ], cost: 1 6.97/3.07 6.97/3.07 13: f23 -> f16 : A'=free_81, E'=1+free_81, E1'=free_83, F1'=free_79, G'=free_78, H'=free_78, Q'=free_78, J'=free_78, K'=free_78, P'=free_80, Q_1'=free_77, U'=free_82, V'=free_84, W'=free_75, [ free_76>=1 ], cost: 1 6.97/3.07 6.97/3.07 9: f16 -> f16 : A'=1+free_33, E'=1+free_32, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_29, P'=free_28, Q_1'=free_34, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, [ A>=0 && free_30>=0 && Q_1>=1+E && free_33>=0 ], cost: 1 6.97/3.07 6.97/3.07 10: f16 -> f18 : A'=free_40, A1'=B, B'=C, B1'=D, C'=free_38, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=0, G1'=N, H'=0, H1'=free_39, Q'=free_37, Q1'=0, J'=S, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=free_41, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, [ A>=0 && free_42>=0 && E>=Q_1 && free_40>=0 ], cost: 1 6.97/3.07 6.97/3.07 11: f16 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ A>=0 && free_54>=0 && free_48>=0 && E>=Q_1 && free_49>=1 ], cost: 1 6.97/3.07 6.97/3.07 12: f16 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && free_70>=0 && free_64>=0 && E>=Q_1 && 0>=1+free_65 ], cost: 1 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Removed unreachable and leaf rules: 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 3: f3 -> f16 : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [], cost: 1 6.97/3.07 6.97/3.07 4: f3 -> f16 : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 ], cost: 1 6.97/3.07 6.97/3.07 9: f16 -> f16 : A'=1+free_33, E'=1+free_32, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_29, P'=free_28, Q_1'=free_34, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, [ A>=0 && free_30>=0 && Q_1>=1+E && free_33>=0 ], cost: 1 6.97/3.07 6.97/3.07 11: f16 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ A>=0 && free_54>=0 && free_48>=0 && E>=Q_1 && free_49>=1 ], cost: 1 6.97/3.07 6.97/3.07 12: f16 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && free_70>=0 && free_64>=0 && E>=Q_1 && 0>=1+free_65 ], cost: 1 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Simplified all rules, resulting in: 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 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