Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Complexity_ITS 2019-03-21 04.46 pair #429990464
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
n063.star.cs.uiowa.edu
space
T2
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
23.4926 seconds
cpu usage
51.2688
user time
50.4272
system time
0.841524
max virtual memory
1.8868364E7
max residence set size
296884.0
stage attributes
key
value
starexec-result
WORST_CASE(NON_POLY, ?)
output
51.10/23.45 WORST_CASE(NON_POLY, ?) 51.10/23.46 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 51.10/23.46 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 51.10/23.46 51.10/23.46 51.10/23.46 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 51.10/23.46 51.10/23.46 (0) CpxIntTrs 51.10/23.46 (1) Loat Proof [FINISHED, 21.8 s] 51.10/23.46 (2) BOUNDS(INF, INF) 51.10/23.46 51.10/23.46 51.10/23.46 ---------------------------------------- 51.10/23.46 51.10/23.46 (0) 51.10/23.46 Obligation: 51.10/23.46 Complexity Int TRS consisting of the following rules: 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 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 51.10/23.46 51.10/23.46 The start-symbols are:[f30_36] 51.10/23.46 51.10/23.46 51.10/23.46 ---------------------------------------- 51.10/23.46 51.10/23.46 (1) Loat Proof (FINISHED) 51.10/23.46 51.10/23.46 51.10/23.46 ### Pre-processing the ITS problem ### 51.10/23.46 51.10/23.46 51.10/23.46 51.10/23.46 Initial linear ITS problem 51.10/23.46 51.10/23.46 Start location: f30 51.10/23.46 51.10/23.46 0: f30 -> f1 : [], cost: 1 51.10/23.46 51.10/23.46 1: f1 -> f2 : A'=free, [], cost: 1 51.10/23.46 51.10/23.46 7: f1 -> f5 : F'=free_2, G'=free_5, H'=free_3, Q'=free_1, J'=free_6, K'=free_4, [], cost: 1 51.10/23.46 51.10/23.46 2: f2 -> f3 : B'=0, C'=0, [], cost: 1 51.10/23.46 51.10/23.46 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 51.10/23.46 51.10/23.46 3: f3 -> f3 : B'=1+B, C'=1+C, [ A>=1+B ], cost: 1 51.10/23.46 51.10/23.46 4: f3 -> f4 : [ B>=A ], cost: 1 51.10/23.46 51.10/23.46 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 51.10/23.46 51.10/23.46 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 51.10/23.46 51.10/23.46 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 51.10/23.46 51.10/23.46 5: f4 -> f5 : D'=0, E'=C, [], cost: 1 51.10/23.46 51.10/23.46 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 51.10/23.46 51.10/23.46 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 51.10/23.46 51.10/23.46 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 51.10/23.46 51.10/23.46 6: f5 -> f5 : D'=1+D, E'=-1+E, [ E>=1 ], cost: 1 51.10/23.46 51.10/23.46 9: f5 -> f16 : F'=1+F, Q'=1+Q, L'=M, [ 0>=E && F>=0 ], cost: 1 51.10/23.46 51.10/23.46 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 51.10/23.46 51.10/23.46 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 51.10/23.46 51.10/23.46 20: f5 -> f3 : F'=free_29, G'=free_36, H'=free_32, Q'=free_27, J'=free_38, L'=free_33, N'=free_35, O'=free_31, S'=free_39, T'=0, V'=J, W'=free_34, X'=free_30, Y'=free_37, [ F>=0 && 0>=1+J && free_28>=0 ], cost: 1 51.10/23.46 51.10/23.46 8: f16 -> f1 : F'=free_7, [ Q>=H && F>=0 ], cost: 1 51.10/23.46 51.10/23.46 22: f16 -> f16 : A1'=free_55, B1'=free_55, C1'=free_55, D1'=free_51, E1'=free_53, F'=1+free_47, F1'=free_49, G'=free_54, G1'=free_56, H'=free_50, H1'=free_52, Q'=1+free_46, L'=free_55, M'=free_55, [ F>=0 && free_48>=0 && H>=1+Q && free_47>=0 ], cost: 1 51.10/23.46
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