Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Complexity_ITS 2019-03-21 04.46 pair #429990816
details
property
value
status
complete
benchmark
destroy_seg.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n126.star.cs.uiowa.edu
space
T2
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
4.69488 seconds
cpu usage
11.0312
user time
10.5724
system time
0.458799
max virtual memory
1.870958E7
max residence set size
258948.0
stage attributes
key
value
starexec-result
WORST_CASE(NON_POLY, ?)
output
10.85/4.64 WORST_CASE(NON_POLY, ?) 10.85/4.65 proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat 10.85/4.65 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.85/4.65 10.85/4.65 10.85/4.65 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 10.85/4.65 10.85/4.65 (0) CpxIntTrs 10.85/4.65 (1) Loat Proof [FINISHED, 2779 ms] 10.85/4.65 (2) BOUNDS(INF, INF) 10.85/4.65 10.85/4.65 10.85/4.65 ---------------------------------------- 10.85/4.65 10.85/4.65 (0) 10.85/4.65 Obligation: 10.85/4.65 Complexity Int TRS consisting of the following rules: 10.85/4.65 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) -> Com_1(f1(A, 1 + B, D, G1, D, H1, B, I, 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 >= B + 1 && B >= 0 10.85/4.65 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) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, M, M, M, G1, H1, H1, J, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: I1 >= J + 1 && K >= 0 && H1 >= I1 + 1 && G1 >= 2 10.85/4.65 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) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, M, M, M, G1, H1, H1, J, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: I1 >= J + 1 && K >= 0 && I1 >= H1 + 1 && G1 >= 2 10.85/4.65 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) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, M, M, M, G1, H1, H1, J, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: J >= I1 + 1 && K >= 0 && H1 >= I1 + 1 && G1 >= 2 10.85/4.65 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) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, M, M, M, G1, H1, H1, J, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: J >= I1 + 1 && K >= 0 && I1 >= H1 + 1 && G1 >= 2 10.85/4.65 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) -> Com_1(f4(A, B, C, D, E, F, G, H, I, M1, K, G1, L1, N, H1, J1, K1, N1, I1, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: K >= 0 && G1 >= J1 + 1 && H1 >= 2 && M >= J && M <= J 10.85/4.65 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) -> Com_1(f4(A, B, C, D, E, F, G, H, I, M1, K, G1, L1, N, H1, J1, K1, N1, I1, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: K >= 0 && J1 >= G1 + 1 && H1 >= 2 && M >= J && M <= J 10.85/4.65 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, B1, C1, D1, E1, F1) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, M, M, M, G1, H1, H1, J, S, -(1) + T, I1, I, -(1) + T, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: J1 >= J + 1 && T >= 0 && H1 >= J1 + 1 && G1 >= 2 10.85/4.65 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, B1, C1, D1, E1, F1) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, M, M, M, G1, H1, H1, J, S, -(1) + T, I1, I, -(1) + T, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: J1 >= J + 1 && T >= 0 && J1 >= H1 + 1 && G1 >= 2 10.85/4.65 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, B1, C1, D1, E1, F1) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, M, M, M, G1, H1, H1, J, S, -(1) + T, I1, I, -(1) + T, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: J >= J1 + 1 && T >= 0 && H1 >= J1 + 1 && G1 >= 2 10.85/4.65 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, B1, C1, D1, E1, F1) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, M, M, M, G1, H1, H1, J, S, -(1) + T, I1, I, -(1) + T, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: J >= J1 + 1 && T >= 0 && J1 >= H1 + 1 && G1 >= 2 10.85/4.65 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, B1, C1, D1, E1, F1) -> Com_1(f4(A, B, C, D, E, F, G, H, I, K1, K, L, J1, N, G1, P, I1, L1, H1, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: G1 >= 2 && T >= 0 && M >= J && M <= J 10.85/4.65 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(f4(J1, M1, L1, T1, S1, F, G, H, I, W1, K, X, V1, X, I1, X, U1, X1, Q1, T, U, V, W, G1, H1, K1, N1, R1, C1, D1, E1, F1)) :|: 0 >= O1 && 0 >= I1 && 0 >= P1 10.85/4.65 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(f1(J1, 2, K1, L1, K1, F, G, H, I, J, K, G1, M, G1, J1, P, Q, R, S, T, U, V, W, H1, I1, G1, A1, K1, M1, D1, E1, F1)) :|: J1 >= 2 10.85/4.65 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) -> Com_1(f10(H1, K1, J1, R1, Q1, F, G, H, I, C, T, N, N, N, G1, C, C, C, M1, T, U, V, W, X, Y, I1, L1, N1, C1, T + 1, I, S1)) :|: B >= A && B >= 0 && T1 >= G1 && U1 >= 2 && K1 >= U1 && C >= N + 1 && K1 >= 0 && G1 >= 2 && N >= C + 1 10.85/4.65 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) -> Com_1(f10(H1, K1, J1, R1, Q1, F, G, H, I, C, T, N, N, N, G1, C, C, C, M1, T, U, V, W, X, Y, I1, L1, N1, C1, T + 1, I, S1)) :|: B >= A && B >= 0 && T1 >= G1 && U1 >= 2 && K1 >= U1 && C >= N + 1 && K1 >= 0 && G1 >= 2 10.85/4.65 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) -> Com_1(f10(H1, K1, J1, R1, Q1, F, G, H, I, C, T, N, N, N, G1, C, C, C, M1, T, U, V, W, X, Y, I1, L1, N1, C1, T + 1, I, S1)) :|: B >= A && B >= 0 && T1 >= G1 && U1 >= 2 && K1 >= U1 && N >= C + 1 && K1 >= 0 && G1 >= 2 10.85/4.65 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(f4(J1, M1, L1, T1, S1, F, G, H, I, X1, K, G1, W1, D, 1, U1, V1, O1, Q1, T, U, V, W, H1, I1, K1, N1, R1, C1, D1, E1, F1)) :|: 0 >= 1 && G1 >= U1 + 1 10.85/4.65 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(f4(J1, M1, L1, T1, S1, F, G, H, I, X1, K, G1, W1, D, 1, U1, V1, O1, Q1, T, U, V, W, H1, I1, K1, N1, R1, C1, D1, E1, F1)) :|: 0 >= 1 && U1 >= G1 + 1 10.85/4.65 10.85/4.65 The start-symbols are:[f3_32] 10.85/4.65 10.85/4.65 10.85/4.65 ---------------------------------------- 10.85/4.65 10.85/4.65 (1) Loat Proof (FINISHED) 10.85/4.65 10.85/4.65 10.85/4.65 ### Pre-processing the ITS problem ### 10.85/4.65 10.85/4.65 10.85/4.65 10.85/4.65 Initial linear ITS problem 10.85/4.65 10.85/4.65 Start location: f3 10.85/4.65 10.85/4.65 0: f1 -> f1 : B'=1+B, C'=D, D'=free_1, E'=D, F'=free, G'=B, H'=Q, [ A>=1+B && B>=0 ], cost: 1 10.85/4.65 10.85/4.65 14: f1 -> f10 : A'=free_85, A1'=free_78, B'=free_80, B1'=free_86, C'=free_88, D'=free_79, D1'=1+T, E'=free_83, E1'=Q, F1'=free_81, J'=C, K'=T, L'=N, M'=N, O'=free_87, P'=C, Q_1'=C, R'=C, S'=free_82, Z'=free_77, [ B>=A && B>=0 && free_89>=free_87 && free_84>=2 && free_80>=free_84 && C>=1+N && free_80>=0 && free_87>=2 && N>=1+C ], cost: 1 10.85/4.65 10.85/4.65 15: f1 -> f10 : A'=free_98, A1'=free_91, B'=free_93, B1'=free_99, C'=free_101, D'=free_92, D1'=1+T, E'=free_96, E1'=Q, F1'=free_94, J'=C, K'=T, L'=N, M'=N, O'=free_100, P'=C, Q_1'=C, R'=C, S'=free_95, Z'=free_90, [ B>=A && B>=0 && free_102>=free_100 && free_97>=2 && free_93>=free_97 && C>=1+N && free_93>=0 && free_100>=2 ], cost: 1 10.85/4.65 10.85/4.65 16: f1 -> f10 : A'=free_111, A1'=free_104, B'=free_106, B1'=free_112, C'=free_114, D'=free_105, D1'=1+T, E'=free_109, E1'=Q, F1'=free_107, J'=C, K'=T, L'=N, M'=N, O'=free_113, P'=C, Q_1'=C, R'=C, S'=free_108, Z'=free_103, [ B>=A && B>=0 && free_115>=free_113 && free_110>=2 && free_106>=free_110 && N>=1+C && free_106>=0 && free_113>=2 ], cost: 1 10.85/4.65 10.85/4.65 1: f9 -> f10 : L'=M, N'=M, O'=free_3, P'=free_2, Q_1'=free_2, R'=J, [ free_4>=1+J && K>=0 && free_2>=1+free_4 && free_3>=2 ], cost: 1 10.85/4.65 10.85/4.65 2: f9 -> f10 : L'=M, N'=M, O'=free_6, P'=free_5, Q_1'=free_5, R'=J, [ free_7>=1+J && K>=0 && free_7>=1+free_5 && free_6>=2 ], cost: 1 10.85/4.65 10.85/4.65 3: f9 -> f10 : L'=M, N'=M, O'=free_9, P'=free_8, Q_1'=free_8, R'=J, [ J>=1+free_10 && K>=0 && free_8>=1+free_10 && free_9>=2 ], cost: 1 10.85/4.65 10.85/4.65 4: f9 -> f10 : L'=M, N'=M, O'=free_12, P'=free_11, Q_1'=free_11, R'=J, [ J>=1+free_13 && K>=0 && free_13>=1+free_11 && free_12>=2 ], cost: 1 10.85/4.65 10.85/4.65 5: f9 -> f4 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_19, F'=K, F1'=free_16, G'=free_21, G1'=N, H'=free_15, H1'=free_18, Q'=free_20, Q1'=free_17, J'=free_14, 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, [ K>=0 && free_16>=1+free_18 && free_15>=2 && M==J ], cost: 1 10.85/4.65 10.85/4.65 6: f9 -> f4 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_27, F'=K, F1'=free_24, G'=free_29, G1'=N, H'=free_23, H1'=free_26, Q'=free_28, Q1'=free_25, J'=free_22, 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, [ K>=0 && free_26>=1+free_24 && free_23>=2 && M==J ], cost: 1 10.85/4.65 10.85/4.65 7: f10 -> f10 : L'=M, N'=M, O'=free_32, P'=free_31, Q_1'=free_31, R'=J, T'=-1+T, U'=free_33, V'=Q, W'=-1+T, [ free_30>=1+J && T>=0 && free_31>=1+free_30 && free_32>=2 ], cost: 1 10.85/4.65 10.85/4.65 8: f10 -> f10 : L'=M, N'=M, O'=free_36, P'=free_35, Q_1'=free_35, R'=J, T'=-1+T, U'=free_37, V'=Q, W'=-1+T, [ free_34>=1+J && T>=0 && free_34>=1+free_35 && free_36>=2 ], cost: 1 10.85/4.65 10.85/4.65 9: f10 -> f10 : L'=M, N'=M, O'=free_40, P'=free_39, Q_1'=free_39, R'=J, T'=-1+T, U'=free_41, V'=Q, W'=-1+T, [ J>=1+free_38 && T>=0 && free_39>=1+free_38 && free_40>=2 ], cost: 1 10.85/4.65 10.85/4.65 10: f10 -> f10 : L'=M, N'=M, O'=free_44, P'=free_43, Q_1'=free_43, R'=J, T'=-1+T, U'=free_45, V'=Q, W'=-1+T, [ J>=1+free_42 && T>=0 && free_42>=1+free_43 && free_44>=2 ], cost: 1 10.85/4.65 10.85/4.65 11: f10 -> f4 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_49, F'=K, F1'=L, G'=free_47, G1'=N, H'=free_51, H1'=P, Q'=free_46, Q1'=free_48, J'=free_50, 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_51>=2 && T>=0 && M==J ], cost: 1 10.85/4.65 10.85/4.65 12: f3 -> f4 : A'=free_63, A1'=free_56, B'=free_68, B1'=free_54, C'=free_61, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_65, F'=K, F1'=X, G'=free_58, G1'=X, H'=free_52, H1'=X, Q'=free_53, Q1'=free_64, J'=free_57, J1'=T, K'=U, K1'=V, L'=W, L1'=free_69, M'=free_62, M1'=free_55, N'=free_66, N1'=free_59, O'=C1, O1'=D1, P'=E1, P1'=F1, [ 0>=free_67 && 0>=free_52 && 0>=free_60 ], cost: 1 10.85/4.65 10.85/4.65 13: f3 -> f1 : A'=free_74, B'=2, B1'=free_71, C'=free_71, C1'=free_72, D'=free_76, E'=free_71, L'=free_70, N'=free_70, O'=free_74, X'=free_73, Y'=free_75, Z'=free_70, [ free_74>=2 ], cost: 1 10.85/4.65 10.85/4.65 17: f3 -> f4 : A'=free_126, A1'=free_120, B'=free_131, B1'=free_118, C'=free_124, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_128, F'=K, F1'=free_122, G'=free_116, G1'=D, H'=1, H1'=free_117, Q'=free_127, Q1'=free_121, J'=free_132, J1'=T, K'=U, K1'=V, L'=W, L1'=free_125, M'=free_119, M1'=free_129, N'=free_123, N1'=free_130, O'=C1, O1'=D1, P'=E1, P1'=F1, [ 0>=1 && free_122>=1+free_117 ], cost: 1 10.85/4.65 10.85/4.65 18: f3 -> f4 : A'=free_143, A1'=free_137, B'=free_148, B1'=free_135, C'=free_141, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_145, F'=K, F1'=free_139, G'=free_133, G1'=D, H'=1, H1'=free_134, Q'=free_144, Q1'=free_138, J'=free_149, J1'=T, K'=U, K1'=V, L'=W, L1'=free_142, M'=free_136, M1'=free_146, N'=free_140, N1'=free_147, O'=C1, O1'=D1, P'=E1, P1'=F1, [ 0>=1 && free_134>=1+free_139 ], cost: 1 10.85/4.65 10.85/4.65 10.85/4.65 10.85/4.65 Removed unreachable and leaf rules: 10.85/4.65 10.85/4.65 Start location: f3 10.85/4.65 10.85/4.65 0: f1 -> f1 : B'=1+B, C'=D, D'=free_1, E'=D, F'=free, G'=B, H'=Q, [ A>=1+B && B>=0 ], cost: 1 10.85/4.65 10.85/4.65 14: f1 -> f10 : A'=free_85, A1'=free_78, B'=free_80, B1'=free_86, C'=free_88, D'=free_79, D1'=1+T, E'=free_83, E1'=Q, F1'=free_81, J'=C, K'=T, L'=N, M'=N, O'=free_87, P'=C, Q_1'=C, R'=C, S'=free_82, Z'=free_77, [ B>=A && B>=0 && free_89>=free_87 && free_84>=2 && free_80>=free_84 && C>=1+N && free_80>=0 && free_87>=2 && N>=1+C ], cost: 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