5.54/2.44 WORST_CASE(NON_POLY, ?) 5.54/2.44 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 5.54/2.44 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.54/2.44 5.54/2.44 5.54/2.44 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 5.54/2.44 5.54/2.44 (0) CpxIntTrs 5.54/2.44 (1) Loat Proof [FINISHED, 696 ms] 5.54/2.44 (2) BOUNDS(INF, INF) 5.54/2.44 5.54/2.44 5.54/2.44 ---------------------------------------- 5.54/2.44 5.54/2.44 (0) 5.54/2.44 Obligation: 5.54/2.44 Complexity Int TRS consisting of the following rules: 5.54/2.44 f11(A, B, C, D, E, F, G, H, I, J, K, L, M, N) -> Com_1(f11(A, P, B, O, E, F, G, H, I, J, K, L, M, N)) :|: A >= 0 && B >= 1 5.54/2.44 f11(A, B, C, D, E, F, G, H, I, J, K, L, M, N) -> Com_1(f11(A, P, B, O, E, F, G, H, I, J, K, L, M, N)) :|: A >= 0 && 0 >= B + 1 5.54/2.44 f16(A, B, C, D, E, F, G, H, I, J, K, L, M, N) -> Com_1(f16(A, B, C, D, E, F, G + 1, O, O, O, K, L, M, N)) :|: E >= 0 && F >= G + 2 5.54/2.44 f11(A, B, C, D, E, F, G, H, I, J, K, L, M, N) -> Com_1(f13(A, 0, C, D, E, F, G, H, I, J, O, L, M, N)) :|: A >= 0 && B >= 0 && B <= 0 5.54/2.44 f16(A, B, C, D, E, F, G, H, I, J, K, L, M, N) -> Com_1(f11(A, R, P, Q, E, F, G, H, I, J, O, J, J, N)) :|: 1 + G >= F && P >= 1 && E >= 0 5.54/2.44 f16(A, B, C, D, E, F, G, H, I, J, K, L, M, N) -> Com_1(f11(A, R, P, Q, E, F, G, H, I, J, O, J, J, N)) :|: 1 + G >= F && 0 >= P + 1 && E >= 0 5.54/2.44 f3000(A, B, C, D, E, F, G, H, I, J, K, L, M, N) -> Com_1(f16(A, B, C, D, E, F, 1, O, O, O, K, L, M, -(100) * P + N)) :|: N >= 100 * P && 99 + 100 * P >= N && F >= 2 5.54/2.44 f3000(A, B, C, D, E, F, G, H, I, J, K, L, M, N) -> Com_1(f13(A, 0, C, D, E, F, 0, H, I, 0, O, 0, 0, -(100) * P + N)) :|: N >= 100 * P && 99 + 100 * P >= N && 1 >= F 5.54/2.44 5.54/2.44 The start-symbols are:[f3000_14] 5.54/2.44 5.54/2.44 5.54/2.44 ---------------------------------------- 5.54/2.44 5.54/2.44 (1) Loat Proof (FINISHED) 5.54/2.44 5.54/2.44 5.54/2.44 ### Pre-processing the ITS problem ### 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Initial linear ITS problem 5.54/2.44 5.54/2.44 Start location: f3000 5.54/2.44 5.54/2.44 0: f11 -> f11 : B'=free_1, C'=B, D'=free, [ A>=0 && B>=1 ], cost: 1 5.54/2.44 5.54/2.44 1: f11 -> f11 : B'=free_3, C'=B, D'=free_2, [ A>=0 && 0>=1+B ], cost: 1 5.54/2.44 5.54/2.44 3: f11 -> f13 : B'=0, K'=free_5, [ A>=0 && B==0 ], cost: 1 5.54/2.44 5.54/2.44 2: f16 -> f16 : G'=1+G, H'=free_4, Q'=free_4, J'=free_4, [ E>=0 && F>=2+G ], cost: 1 5.54/2.44 5.54/2.44 4: f16 -> f11 : B'=free_9, C'=free_6, D'=free_7, K'=free_8, L'=J, M'=J, [ 1+G>=F && free_6>=1 && E>=0 ], cost: 1 5.54/2.44 5.54/2.44 5: f16 -> f11 : B'=free_13, C'=free_10, D'=free_11, K'=free_12, L'=J, M'=J, [ 1+G>=F && 0>=1+free_10 && E>=0 ], cost: 1 5.54/2.44 5.54/2.44 6: f3000 -> f16 : G'=1, H'=free_15, Q'=free_15, J'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 ], cost: 1 5.54/2.44 5.54/2.44 7: f3000 -> f13 : B'=0, G'=0, J'=0, K'=free_17, L'=0, M'=0, N'=-100*free_16+N, [ N>=100*free_16 && 99+100*free_16>=N && 1>=F ], cost: 1 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Removed unreachable and leaf rules: 5.54/2.44 5.54/2.44 Start location: f3000 5.54/2.44 5.54/2.44 0: f11 -> f11 : B'=free_1, C'=B, D'=free, [ A>=0 && B>=1 ], cost: 1 5.54/2.44 5.54/2.44 1: f11 -> f11 : B'=free_3, C'=B, D'=free_2, [ A>=0 && 0>=1+B ], cost: 1 5.54/2.44 5.54/2.44 2: f16 -> f16 : G'=1+G, H'=free_4, Q'=free_4, J'=free_4, [ E>=0 && F>=2+G ], cost: 1 5.54/2.44 5.54/2.44 4: f16 -> f11 : B'=free_9, C'=free_6, D'=free_7, K'=free_8, L'=J, M'=J, [ 1+G>=F && free_6>=1 && E>=0 ], cost: 1 5.54/2.44 5.54/2.44 5: f16 -> f11 : B'=free_13, C'=free_10, D'=free_11, K'=free_12, L'=J, M'=J, [ 1+G>=F && 0>=1+free_10 && E>=0 ], cost: 1 5.54/2.44 5.54/2.44 6: f3000 -> f16 : G'=1, H'=free_15, Q'=free_15, J'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 ], cost: 1 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 ### Simplification by acceleration and chaining ### 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Accelerating simple loops of location 0. 5.54/2.44 5.54/2.44 Accelerating the following rules: 5.54/2.44 5.54/2.44 0: f11 -> f11 : B'=free_1, C'=B, D'=free, [ A>=0 && B>=1 ], cost: 1 5.54/2.44 5.54/2.44 1: f11 -> f11 : B'=free_3, C'=B, D'=free_2, [ A>=0 && 0>=1+B ], cost: 1 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Accelerated rule 0 with NONTERM (after strengthening guard), yielding the new rule 8. 5.54/2.44 5.54/2.44 Accelerated rule 1 with NONTERM (after strengthening guard), yielding the new rule 9. 5.54/2.44 5.54/2.44 Removing the simple loops:. 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Accelerating simple loops of location 1. 5.54/2.44 5.54/2.44 Accelerating the following rules: 5.54/2.44 5.54/2.44 2: f16 -> f16 : G'=1+G, H'=free_4, Q'=free_4, J'=free_4, [ E>=0 && F>=2+G ], cost: 1 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Accelerated rule 2 with metering function -1+F-G, yielding the new rule 10. 5.54/2.44 5.54/2.44 Removing the simple loops: 2. 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Accelerated all simple loops using metering functions (where possible): 5.54/2.44 5.54/2.44 Start location: f3000 5.54/2.44 5.54/2.44 0: f11 -> f11 : B'=free_1, C'=B, D'=free, [ A>=0 && B>=1 ], cost: 1 5.54/2.44 5.54/2.44 1: f11 -> f11 : B'=free_3, C'=B, D'=free_2, [ A>=0 && 0>=1+B ], cost: 1 5.54/2.44 5.54/2.44 8: f11 -> [4] : [ A>=0 && B>=1 && free_1>=1 ], cost: INF 5.54/2.44 5.54/2.44 9: f11 -> [4] : [ A>=0 && 0>=1+B && 0>=1+free_3 ], cost: INF 5.54/2.44 5.54/2.44 4: f16 -> f11 : B'=free_9, C'=free_6, D'=free_7, K'=free_8, L'=J, M'=J, [ 1+G>=F && free_6>=1 && E>=0 ], cost: 1 5.54/2.44 5.54/2.44 5: f16 -> f11 : B'=free_13, C'=free_10, D'=free_11, K'=free_12, L'=J, M'=J, [ 1+G>=F && 0>=1+free_10 && E>=0 ], cost: 1 5.54/2.44 5.54/2.44 10: f16 -> f16 : G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, [ E>=0 && F>=2+G ], cost: -1+F-G 5.54/2.44 5.54/2.44 6: f3000 -> f16 : G'=1, H'=free_15, Q'=free_15, J'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 ], cost: 1 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Chained accelerated rules (with incoming rules): 5.54/2.44 5.54/2.44 Start location: f3000 5.54/2.44 5.54/2.44 4: f16 -> f11 : B'=free_9, C'=free_6, D'=free_7, K'=free_8, L'=J, M'=J, [ 1+G>=F && free_6>=1 && E>=0 ], cost: 1 5.54/2.44 5.54/2.44 5: f16 -> f11 : B'=free_13, C'=free_10, D'=free_11, K'=free_12, L'=J, M'=J, [ 1+G>=F && 0>=1+free_10 && E>=0 ], cost: 1 5.54/2.44 5.54/2.44 11: f16 -> f11 : B'=free_1, C'=free_9, D'=free, K'=free_8, L'=J, M'=J, [ 1+G>=F && E>=0 && A>=0 && free_9>=1 ], cost: 2 5.54/2.44 5.54/2.44 12: f16 -> f11 : B'=free_1, C'=free_13, D'=free, K'=free_12, L'=J, M'=J, [ 1+G>=F && E>=0 && A>=0 && free_13>=1 ], cost: 2 5.54/2.44 5.54/2.44 13: f16 -> f11 : B'=free_3, C'=free_9, D'=free_2, K'=free_8, L'=J, M'=J, [ 1+G>=F && E>=0 && A>=0 && 0>=1+free_9 ], cost: 2 5.54/2.44 5.54/2.44 14: f16 -> f11 : B'=free_3, C'=free_13, D'=free_2, K'=free_12, L'=J, M'=J, [ 1+G>=F && E>=0 && A>=0 && 0>=1+free_13 ], cost: 2 5.54/2.44 5.54/2.44 15: f16 -> [4] : B'=free_9, C'=free_6, D'=free_7, K'=free_8, L'=J, M'=J, [ 1+G>=F && free_6>=1 && E>=0 && A>=0 && free_9>=1 ], cost: INF 5.54/2.44 5.54/2.44 16: f16 -> [4] : B'=free_13, C'=free_10, D'=free_11, K'=free_12, L'=J, M'=J, [ 1+G>=F && 0>=1+free_10 && E>=0 && A>=0 && free_13>=1 ], cost: INF 5.54/2.44 5.54/2.44 17: f16 -> [4] : B'=free_9, C'=free_6, D'=free_7, K'=free_8, L'=J, M'=J, [ 1+G>=F && free_6>=1 && E>=0 && A>=0 && 0>=1+free_9 ], cost: INF 5.54/2.44 5.54/2.44 18: f16 -> [4] : B'=free_13, C'=free_10, D'=free_11, K'=free_12, L'=J, M'=J, [ 1+G>=F && 0>=1+free_10 && E>=0 && A>=0 && 0>=1+free_13 ], cost: INF 5.54/2.44 5.54/2.44 6: f3000 -> f16 : G'=1, H'=free_15, Q'=free_15, J'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 ], cost: 1 5.54/2.44 5.54/2.44 19: f3000 -> f16 : G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 ], cost: -1+F 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Removed unreachable locations (and leaf rules with constant cost): 5.54/2.44 5.54/2.44 Start location: f3000 5.54/2.44 5.54/2.44 15: f16 -> [4] : B'=free_9, C'=free_6, D'=free_7, K'=free_8, L'=J, M'=J, [ 1+G>=F && free_6>=1 && E>=0 && A>=0 && free_9>=1 ], cost: INF 5.54/2.44 5.54/2.44 16: f16 -> [4] : B'=free_13, C'=free_10, D'=free_11, K'=free_12, L'=J, M'=J, [ 1+G>=F && 0>=1+free_10 && E>=0 && A>=0 && free_13>=1 ], cost: INF 5.54/2.44 5.54/2.44 17: f16 -> [4] : B'=free_9, C'=free_6, D'=free_7, K'=free_8, L'=J, M'=J, [ 1+G>=F && free_6>=1 && E>=0 && A>=0 && 0>=1+free_9 ], cost: INF 5.54/2.44 5.54/2.44 18: f16 -> [4] : B'=free_13, C'=free_10, D'=free_11, K'=free_12, L'=J, M'=J, [ 1+G>=F && 0>=1+free_10 && E>=0 && A>=0 && 0>=1+free_13 ], cost: INF 5.54/2.44 5.54/2.44 6: f3000 -> f16 : G'=1, H'=free_15, Q'=free_15, J'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 ], cost: 1 5.54/2.44 5.54/2.44 19: f3000 -> f16 : G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 ], cost: -1+F 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Eliminated locations (on tree-shaped paths): 5.54/2.44 5.54/2.44 Start location: f3000 5.54/2.44 5.54/2.44 20: f3000 -> [4] : B'=free_9, C'=free_6, D'=free_7, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_8, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && free_6>=1 && E>=0 && A>=0 && free_9>=1 ], cost: INF 5.54/2.44 5.54/2.44 21: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_12, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && 0>=1+free_10 && E>=0 && A>=0 && free_13>=1 ], cost: INF 5.54/2.44 5.54/2.44 22: f3000 -> [4] : B'=free_9, C'=free_6, D'=free_7, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_8, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && free_6>=1 && E>=0 && A>=0 && 0>=1+free_9 ], cost: INF 5.54/2.44 5.54/2.44 23: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_12, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && 0>=1+free_10 && E>=0 && A>=0 && 0>=1+free_13 ], cost: INF 5.54/2.44 5.54/2.44 24: f3000 -> [4] : B'=free_9, C'=free_6, D'=free_7, G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, K'=free_8, L'=free_4, M'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 && free_6>=1 && A>=0 && free_9>=1 ], cost: INF 5.54/2.44 5.54/2.44 25: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, K'=free_12, L'=free_4, M'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 && 0>=1+free_10 && A>=0 && free_13>=1 ], cost: INF 5.54/2.44 5.54/2.44 26: f3000 -> [4] : B'=free_9, C'=free_6, D'=free_7, G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, K'=free_8, L'=free_4, M'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 && free_6>=1 && A>=0 && 0>=1+free_9 ], cost: INF 5.54/2.44 5.54/2.44 27: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, K'=free_12, L'=free_4, M'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 && 0>=1+free_10 && A>=0 && 0>=1+free_13 ], cost: INF 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Applied pruning (of leafs and parallel rules): 5.54/2.44 5.54/2.44 Start location: f3000 5.54/2.44 5.54/2.44 20: f3000 -> [4] : B'=free_9, C'=free_6, D'=free_7, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_8, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && free_6>=1 && E>=0 && A>=0 && free_9>=1 ], cost: INF 5.54/2.44 5.54/2.44 21: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_12, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && 0>=1+free_10 && E>=0 && A>=0 && free_13>=1 ], cost: INF 5.54/2.44 5.54/2.44 23: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_12, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && 0>=1+free_10 && E>=0 && A>=0 && 0>=1+free_13 ], cost: INF 5.54/2.44 5.54/2.44 24: f3000 -> [4] : B'=free_9, C'=free_6, D'=free_7, G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, K'=free_8, L'=free_4, M'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 && free_6>=1 && A>=0 && free_9>=1 ], cost: INF 5.54/2.44 5.54/2.44 25: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, K'=free_12, L'=free_4, M'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 && 0>=1+free_10 && A>=0 && free_13>=1 ], cost: INF 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 ### Computing asymptotic complexity ### 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Fully simplified ITS problem 5.54/2.44 5.54/2.44 Start location: f3000 5.54/2.44 5.54/2.44 20: f3000 -> [4] : B'=free_9, C'=free_6, D'=free_7, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_8, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && free_6>=1 && E>=0 && A>=0 && free_9>=1 ], cost: INF 5.54/2.44 5.54/2.44 21: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_12, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && 0>=1+free_10 && E>=0 && A>=0 && free_13>=1 ], cost: INF 5.54/2.44 5.54/2.44 23: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=1, H'=free_15, Q'=free_15, J'=free_15, K'=free_12, L'=free_15, M'=free_15, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && 0>=1+free_10 && E>=0 && A>=0 && 0>=1+free_13 ], cost: INF 5.54/2.44 5.54/2.44 24: f3000 -> [4] : B'=free_9, C'=free_6, D'=free_7, G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, K'=free_8, L'=free_4, M'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 && free_6>=1 && A>=0 && free_9>=1 ], cost: INF 5.54/2.44 5.54/2.44 25: f3000 -> [4] : B'=free_13, C'=free_10, D'=free_11, G'=-1+F, H'=free_4, Q'=free_4, J'=free_4, K'=free_12, L'=free_4, M'=free_4, N'=N-100*free_14, [ N>=100*free_14 && 99+100*free_14>=N && E>=0 && F>=3 && 0>=1+free_10 && A>=0 && free_13>=1 ], cost: INF 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Computing asymptotic complexity for rule 20 5.54/2.44 5.54/2.44 Resulting cost INF has complexity: Nonterm 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Found new complexity Nonterm. 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 Obtained the following overall complexity (w.r.t. the length of the input n): 5.54/2.44 5.54/2.44 Complexity: Nonterm 5.54/2.44 5.54/2.44 Cpx degree: Nonterm 5.54/2.44 5.54/2.44 Solved cost: INF 5.54/2.44 5.54/2.44 Rule cost: INF 5.54/2.44 5.54/2.44 Rule guard: [ N>=100*free_14 && 99+100*free_14>=N && F>=2 && 2>=F && free_6>=1 && E>=0 && A>=0 && free_9>=1 ] 5.54/2.44 5.54/2.44 5.54/2.44 5.54/2.44 NO 5.54/2.44 5.54/2.44 5.54/2.44 ---------------------------------------- 5.54/2.44 5.54/2.44 (2) 5.54/2.44 BOUNDS(INF, INF) 5.58/2.47 EOF