details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	254.731607914 seconds
cpu usage	282.119839383
max memory	5.64342784E8

stage attributes

key	value
output-size	69940
starexec-result	WORST_CASE(Omega(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), ?) 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, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 1885 ms] (2) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: 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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f116(A, B, 1, -(1), F, F, Z1, 1 + F, A2, Z1, 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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: A >= 2 && Y1 >= A && B >= 0 && C >= 1 && C <= 1 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, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f116(A, B, 2, D, Z1, -(1) + Z1, G, H, I, A2, 2, -(1), Y1, B2, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: E >= 0 && A >= 2 f116(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f300(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, 1, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: F >= O && P >= 1 && P <= 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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f1(A, 1 + B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, S, Z1, S, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: B >= 0 && Q >= B + 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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f116(A, Z1, 0, D, E, F, G, H, I, J, K, L, M, N, O, P, A2, Y1, D2, B2, R, R, E2, F2, G2, Z1, C2, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: A >= 2 && C2 >= A && F >= A && B >= Q && B >= 0 && C >= 0 && C <= 0 f7(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f8(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, Z1, D1, D1, -(1) + Z1, -(1), G1, H1, I1, J1, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: B1 >= 0 f7(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(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, E2, Z, A1, B1, F2, D2, E1, F1, B2, Z1, A2, Y1, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: B1 >= 0 && G1 >= D1 && G1 <= D1 f8(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f8(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, 0, H1, W, X, Y, Z, A1, B1, D1, D1, -(1) + E1, F1, 0, H1, 0, H1, -(1) + E1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: E1 >= 0 && A >= 2 && I1 >= 0 && I1 <= 0 && H1 >= V && H1 <= V && G1 >= 0 && G1 <= 0 && U >= 0 && U <= 0 && J1 >= V && J1 <= V f8(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f10(E2, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, F2, Z, A1, B1, G2, D2, E1, F1, B2, Z1, A2, Y1, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: E1 >= 0 && G1 >= D1 && G1 <= D1 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, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f8(A, B, E1 + 1, D, 0, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, 0, V, W, X, Y, Z, A1, E1, V, V, E1, F1, 0, V, 0, V, K1, -(1), M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: A >= 2 && U >= 0 && U <= 0 && E >= 0 && E <= 0 && C >= 1 && C <= 1 f116(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f116(A, B, 1 + C, D, E, -(1) + F, G, H, I, J, K, L, M, N, F, 1, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1, U, 1 + C, -(1) + F, P1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: A >= 2 && C >= 0 && F >= 0 && P >= 0 && P <= 0 && U >= M1 && U <= M1 f116(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f8(A, B, E1 + 1, D, E, F, G, H, I, J, K, L, M, N, F, 1, Q, R, S, T, 0, V, W, X, Y, Z, A1, E1, V, V, E1, F1, 0, V, 0, V, K1, -(1), M1, N1, O1, Z1, Q1, R1, S1, T1, U1, V1, W1, X1)) :|: Z1 >= 0 && A >= 2 && C >= 0 && F >= 0 && U >= 0 && U <= 0 && P >= 0 && P <= 0 f9(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f1(Z1, 2, C, D, E, F, G, H, I, J, K, L, M, N, O, 0, Z1, S, B2, S, U, V, S, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1, M1, N1, O1, P1, A2, Y1, D2, 2, E2, V1, W1, X1)) :|: Z1 >= 2 && S >= W && S <= W f9(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f10(F2, E2, C, D, E, F, G, H, I, J, K, L, M, N, O, 0, C2, H2, J2, I2, 0, 0, K2, L2, M2, Z, A1, B1, N2, D2, E1, F1, B2, Z1, A2, Y1, K1, L1, M1, N1, O1, P1, Q1, G2, S1, T1, U1, V1, W1, X1)) :|: 0 >= F2 f9(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, K1, L1, M1, N1, O1, P1, Q1, R1, S1, T1, U1, V1, W1, X1) -> Com_1(f10(1, E2, C, D, E, F, G, H, I, J, K, L, M, N, O, 0, H2, I2, K2, J2, 0, 0, M2, N2, O2, Z, A1, B1, Q2, D2, E1, F1, B2, Z1, A2, Y1, K1, L1, M1, N1, O1, P1, G2, C2, L2, T1, U1, F2, G2, P2)) :|: S >= 0 && S <= 0 && W >= 0 && W <= 0 The start-symbols are:[f9_50] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f9 0: f12 -> f116 : C'=1, D'=-1, E'=F, G'=free, H'=1+F, Q'=free_1, J'=free, [ A>=2 && free_2>=A && B>=0 && C==1 ], cost: 1 1: f13 -> f116 : C'=2, E'=free_3, F'=-1+free_3, J'=free_5, K'=2, L'=-1, M'=free_6, N'=free_4, [ E>=0 && A>=2 ], cost: 1 9: f13 -> f8 : B1'=E1, C'=1+E1, C1'=V, D1'=V, E'=0, G1'=0, H1'=V, Q1'=0, J1'=V, L1'=-1, U'=0, [ A>=2 && U==0 && E==0 && C==1 ], cost: 1 2: f116 -> f300 : A1'=B, A2'=C, B'=D, B1'=E, B2'=F, C'=G, C1'=H, C2'=Q, D'=J, D1'=K, D2'=L, E'=M, E1'=N, E2'=O, F'=1, F1'=Q_1, F2'=R, G'=S, G1'=T, G2'=U, H'=V, H1'=W, H2'=X, Q'=Y, Q1'=Z, Q2'=A1, J'=B1, J1'=C1, J2'=D1, K'=E1, K1'=F1, K2'=G1, L'=H1, L1'=Q1, L2'=J1, M'=K1, M1'=L1, M2'=M1, N'=N1, N1'=O1, N2'=P1, O'=Q1_1, O1'=R1, O2'=S1, P'=T1, P1'=U1, P2'=V1, Q_1'=W1, Q1_1'=X1, [ F>=O && P==1 ], cost: 1 10: f116 -> f116 : C'=1+C, F'=-1+F, M1'=U, N1'=1+C, O'=F, O1'=-1+F, P'=1, [ A>=2 && C>=0 && F>=0 && P==0 && U==M1 ], cost: 1 11: f116 -> f8 : B1'=E1, C'=1+E1, C1'=V, D1'=V, G1'=0, H1'=V, Q1'=0, J1'=V, L1'=-1, O'=F, P'=1, P1'=free_33, U'=0, [ free_33>=0 && A>=2 && C>=0 && F>=0 && U==0 && P==0 ], cost: 1 3: f1 -> f1 : B'=1+B, R'=S, S'=free_7, T'=S, [ B>=0 && Q_1>=1+B ], cost: 1 4: f1 -> f116 : A1'=free_10, B'=free_9, C'=0, Q_1'=free_12, R'=free_13, S'=free_11, T'=free_8, U'=R, V'=R, W'=free_16, X'=free_15, Y'=free_14, Z'=free_9, [ A>=2 && free_10>=A && F>=A && B>=Q_1 && B>=0 && C==0 ], cost: 1 5: f7 -> f8 : B1'=free_17, C1'=D1, E1'=-1+free_17, F1'=-1, [ B1>=0 ], cost: 1 6: f7 -> f10 : A1'=B, A2'=C, B'=D, B1'=E, B2'=F, C'=G, C1'=H, C2'=Q, D'=J, D1'=K, D2'=L, E'=M, E1'=N, E2'=O, F'=P, F1'=Q_1, F2'=R, G'=S, G1'=T, G2'=U, H'=V, H1'=W, H2'=X, Q'=free_19, Q1'=Z, Q2'=A1, J'=B1, J1'=free_21, J2'=free_22, K'=E1, K1'=F1, K2'=free_20, L'=free_18, L1'=free_24, L2'=free_23, M'=K1, M1'=L1, M2'=M1, N'=N1, N1'=O1, N2'=P1, O'=Q1_1, O1'=R1, O2'=S1, P'=T1, P1'=U1, P2'=V1, Q_1'=W1, Q1_1'=X1, [ B1>=0 && G1==D1 ], cost: 1 7: f8 -> f8 : C1'=D1, E1'=-1+E1, G1'=0, Q1'=0, J1'=H1, K1'=-1+E1, U'=0, V'=H1, [ E1>=0 && A>=2 && Q1==0 && H1==V && G1==0 && U==0 && J1==V ], cost: 1 8: f8 -> f10 : A'=free_26, A1'=B, A2'=C, B'=D, B1'=E, B2'=F, C'=G, C1'=H, C2'=Q, D'=J, D1'=K, D2'=L, E'=M, E1'=N, E2'=O, F'=P, F1'=Q_1, F2'=R, G'=S, G1'=T, G2'=U, H'=V, H1'=W, H2'=X, Q'=free_28, Q1'=Z, Q2'=A1, J'=B1, J1'=free_29, J2'=free_27, K'=E1, K1'=F1, K2'=free_25, L'=free_32, L1'=free_31, L2'=free_30, M'=K1, M1'=L1, M2'=M1, N'=N1, N1'=O1, N2'=P1, O'=Q1_1, O1'=R1, O2'=S1, P'=T1, P1'=U1, P2'=V1, Q_1'=W1, Q1_1'=X1, [ E1>=0 && G1==D1 ], cost: 1 12: f9 -> f1 : A'=free_35, B'=2, P'=0, Q_1'=free_35, Q1_1'=free_38, R'=S, R1'=free_36, S'=free_37, S1'=free_34, T'=S, T1'=2, U1'=free_39, W'=S, [ free_35>=2 && S==W ], cost: 1 13: f9 -> f10 : A'=free_41, A1'=free_44, A2'=C, B'=D, B1'=E, B2'=F, C'=G, C1'=H, C2'=Q, D'=J, D1'=K, D2'=L, E'=M, E1'=N, E2'=O, F'=0, F1'=free_45, F2'=free_43, G'=free_40, G1'=free_55, G2'=0, H'=0, H1'=free_54, H2'=free_52, Q'=free_42, Q1'=Z, Q2'=A1, J'=B1, J1'=free_50, J2'=free_48, K'=E1, K1'=F1, K2'=free_53, L'=free_51, L1'=free_49, L2'=free_47, M'=K1, M1'=L1, M2'=M1, N'=N1, N1'=O1, N2'=P1, O'=Q1_1, O1'=free_46, O2'=S1, P'=T1, P1'=U1, P2'=V1, Q_1'=W1, Q1_1'=X1, [ 0>=free_41 ], cost: 1 14: f9 -> f10 : A'=1, A1'=free_57, A2'=C, B'=D, B1'=E, B2'=F, C'=G, C1'=H, C2'=Q, D'=J, D1'=K, D2'=L, E'=M, E1'=N, E2'=O, F'=0, F1'=free_60, F2'=free_64, G'=free_59, G1'=free_56, G2'=0, H'=0, H1'=free_74, H2'=free_73, Q'=free_71, Q1'=Z, Q2'=A1, J'=B1, J1'=free_58, J2'=free_69, K'=E1, K1'=F1, K2'=free_67, L'=free_72, L1'=free_70, L2'=free_68, M'=K1, M1'=L1, M2'=M1, N'=N1, N1'=O1, N2'=P1, O'=free_66, O1'=free_65, O2'=free_63, P'=T1, P1'=U1, P2'=free_62, Q_1'=free_66, Q1_1'=free_61, [ S==0 && W==0 ], cost: 1 Removed unreachable and leaf rules: Start location: f9 10: f116 -> f116 : C'=1+C, F'=-1+F, M1'=U, N1'=1+C, O'=F, O1'=-1+F, P'=1, [ A>=2 && C>=0 && F>=0 && P==0 && U==M1 ], cost: 1 11: f116 -> f8 : B1'=E1, C'=1+E1, C1'=V, D1'=V, G1'=0, H1'=V, Q1'=0, J1'=V, L1'=-1, O'=F, P'=1, P1'=free_33, U'=0, [ free_33>=0 && A>=2 && C>=0 && F>=0 && U==0 && P==0 ], cost: 1 3: f1 -> f1 : B'=1+B, R'=S, S'=free_7, T'=S, [ B>=0 && Q_1>=1+B ], cost: 1 4: f1 -> f116 : A1'=free_10, B'=free_9, C'=0, Q_1'=free_12, R'=free_13, S'=free_11, T'=free_8, U'=R, V'=R, W'=free_16, X'=free_15, Y'=free_14, Z'=free_9, [ A>=2 && free_10>=A && F>=A && B>=Q_1 && B>=0 && C==0 ], cost: 1 7: f8 -> f8 : C1'=D1, E1'=-1+E1, G1'=0, Q1'=0, J1'=H1, K1'=-1+E1, U'=0, V'=H1, [ E1>=0 && A>=2 && Q1==0 && H1==V && G1==0 && U==0 && J1==V ], 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