4.73/2.15	WORST_CASE(NON_POLY, ?)
4.73/2.16	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.73/2.16	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.73/2.16	
4.73/2.16	
4.73/2.16	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
4.73/2.16	
4.73/2.16	(0) CpxIntTrs
4.73/2.16	(1) Loat Proof [FINISHED, 392 ms]
4.73/2.16	(2) BOUNDS(INF, INF)
4.73/2.16	
4.73/2.16	
4.73/2.16	----------------------------------------
4.73/2.16	
4.73/2.16	(0)
4.73/2.16	Obligation:
4.73/2.16	Complexity Int TRS consisting of the following rules:
4.73/2.16	f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f18(3, 3, 0, 3, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: TRUE
4.73/2.16	f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= A && A >= C
4.73/2.16	f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f10(A, B + A, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= 1 && A >= C
4.73/2.16	f18(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f25(A, B, C, D, D, D, -(3), 4, 0, J, K, L, M, N, O, P, Q, R)) :|: TRUE
4.73/2.16	f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= G && G >= I
4.73/2.16	f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f25(A, B, C, D, E, F, G, H + G, I, J, K, L, M, N, O, P, Q, R)) :|: G >= 1 && G >= I
4.73/2.16	f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f40(A, B, C, D, E, F, G, H, I, K, K, K, 3, -(6), 0, P, Q, R)) :|: TRUE
4.73/2.16	f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= M && M >= O
4.73/2.16	f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N + M, O, P, Q, R)) :|: M >= 1 && M >= O
4.73/2.16	f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, Q, Q, Q)) :|: 4 >= F
4.73/2.16	f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, Q, Q, Q)) :|: F >= 5
4.73/2.16	f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, N, R)) :|: O >= 1 + M
4.73/2.16	f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, E, F, G, H, I, J, H, L, M, N, O, P, Q, R)) :|: I >= 1 + G
4.73/2.16	f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f18(A, B, C, B, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: C >= 1 + A
4.73/2.16	
4.73/2.16	The start-symbols are:[f0_18]
4.73/2.16	
4.73/2.16	
4.73/2.16	----------------------------------------
4.73/2.16	
4.73/2.16	(1) Loat Proof (FINISHED)
4.73/2.16	
4.73/2.16	
4.73/2.16	### Pre-processing the ITS problem ###
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Initial linear ITS problem
4.73/2.16	
4.73/2.16	   Start location: f0
4.73/2.16	
4.73/2.16	      0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1
4.73/2.16	
4.73/2.16	      1: f10 -> f10 : [ 0>=A && A>=C ], cost: 1
4.73/2.16	
4.73/2.16	      2: f10 -> f10 : B'=A+B, [ A>=1 && A>=C ], cost: 1
4.73/2.16	
4.73/2.16	     13: f10 -> f18 : D'=B, [ C>=1+A ], cost: 1
4.73/2.16	
4.73/2.16	      3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1
4.73/2.16	
4.73/2.16	      4: f25 -> f25 : [ 0>=G && G>=Q ], cost: 1
4.73/2.16	
4.73/2.16	      5: f25 -> f25 : H'=G+H, [ G>=1 && G>=Q ], cost: 1
4.73/2.16	
4.73/2.16	     12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1
4.73/2.16	
4.73/2.16	      6: f33 -> f40 : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: 1
4.73/2.16	
4.73/2.16	      7: f40 -> f40 : [ 0>=M && M>=O ], cost: 1
4.73/2.16	
4.73/2.16	      8: f40 -> f40 : N'=M+N, [ M>=1 && M>=O ], cost: 1
4.73/2.16	
4.73/2.16	     11: f40 -> f48 : Q_1'=N, [ O>=1+M ], cost: 1
4.73/2.16	
4.73/2.16	      9: f48 -> f52 : P'=Q_1, R'=Q_1, [ 4>=F ], cost: 1
4.73/2.16	
4.73/2.16	     10: f48 -> f52 : P'=Q_1, R'=Q_1, [ F>=5 ], cost: 1
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Removed unreachable and leaf rules:
4.73/2.16	
4.73/2.16	   Start location: f0
4.73/2.16	
4.73/2.16	      0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1
4.73/2.16	
4.73/2.16	      3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1
4.73/2.16	
4.73/2.16	      4: f25 -> f25 : [ 0>=G && G>=Q ], cost: 1
4.73/2.16	
4.73/2.16	      5: f25 -> f25 : H'=G+H, [ G>=1 && G>=Q ], cost: 1
4.73/2.16	
4.73/2.16	     12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1
4.73/2.16	
4.73/2.16	      6: f33 -> f40 : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: 1
4.73/2.16	
4.73/2.16	      7: f40 -> f40 : [ 0>=M && M>=O ], cost: 1
4.73/2.16	
4.73/2.16	      8: f40 -> f40 : N'=M+N, [ M>=1 && M>=O ], cost: 1
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	### Simplification by acceleration and chaining ###
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Accelerating simple loops of location 3.
4.73/2.16	
4.73/2.16	   Accelerating the following rules:
4.73/2.16	
4.73/2.16	      4: f25 -> f25 : [ 0>=G && G>=Q ], cost: 1
4.73/2.16	
4.73/2.16	      5: f25 -> f25 : H'=G+H, [ G>=1 && G>=Q ], cost: 1
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	   Accelerated rule 4 with NONTERM, yielding the new rule 14.
4.73/2.16	
4.73/2.16	   Accelerated rule 5 with NONTERM, yielding the new rule 15.
4.73/2.16	
4.73/2.16	   Removing the simple loops: 4 5.
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Accelerating simple loops of location 5.
4.73/2.16	
4.73/2.16	   Accelerating the following rules:
4.73/2.16	
4.73/2.16	      7: f40 -> f40 : [ 0>=M && M>=O ], cost: 1
4.73/2.16	
4.73/2.16	      8: f40 -> f40 : N'=M+N, [ M>=1 && M>=O ], cost: 1
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	   Accelerated rule 7 with NONTERM, yielding the new rule 16.
4.73/2.16	
4.73/2.16	   Accelerated rule 8 with NONTERM, yielding the new rule 17.
4.73/2.16	
4.73/2.16	   Removing the simple loops: 7 8.
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Accelerated all simple loops using metering functions (where possible):
4.73/2.16	
4.73/2.16	   Start location: f0
4.73/2.16	
4.73/2.16	      0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1
4.73/2.16	
4.73/2.16	      3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1
4.73/2.16	
4.73/2.16	     12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1
4.73/2.16	
4.73/2.16	     14: f25 -> [8] : [ 0>=G && G>=Q ], cost: INF
4.73/2.16	
4.73/2.16	     15: f25 -> [8] : [ G>=1 && G>=Q ], cost: INF
4.73/2.16	
4.73/2.16	      6: f33 -> f40 : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: 1
4.73/2.16	
4.73/2.16	     16: f40 -> [9] : [ 0>=M && M>=O ], cost: INF
4.73/2.16	
4.73/2.16	     17: f40 -> [9] : [ M>=1 && M>=O ], cost: INF
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Chained accelerated rules (with incoming rules):
4.73/2.16	
4.73/2.16	   Start location: f0
4.73/2.16	
4.73/2.16	      0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1
4.73/2.16	
4.73/2.16	      3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1
4.73/2.16	
4.73/2.16	     12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1
4.73/2.16	
4.73/2.16	      6: f33 -> f40 : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: 1
4.73/2.16	
4.73/2.16	     18: f33 -> [9] : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: INF
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Removed unreachable locations (and leaf rules with constant cost):
4.73/2.16	
4.73/2.16	   Start location: f0
4.73/2.16	
4.73/2.16	      0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1
4.73/2.16	
4.73/2.16	      3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1
4.73/2.16	
4.73/2.16	     12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1
4.73/2.16	
4.73/2.16	     18: f33 -> [9] : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: INF
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Eliminated locations (on linear paths):
4.73/2.16	
4.73/2.16	   Start location: f0
4.73/2.16	
4.73/2.16	     21: f0 -> [9] : A'=3, B'=3, C'=0, D'=3, E'=3, F'=3, G'=-3, H'=4, Q'=0, J'=4, K'=4, L'=4, M'=3, N'=-6, O'=0, [], cost: INF
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	### Computing asymptotic complexity ###
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Fully simplified ITS problem
4.73/2.16	
4.73/2.16	   Start location: f0
4.73/2.16	
4.73/2.16	     21: f0 -> [9] : A'=3, B'=3, C'=0, D'=3, E'=3, F'=3, G'=-3, H'=4, Q'=0, J'=4, K'=4, L'=4, M'=3, N'=-6, O'=0, [], cost: INF
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Computing asymptotic complexity for rule 21
4.73/2.16	
4.73/2.16	   Resulting cost INF has complexity: Nonterm
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Found new complexity Nonterm.
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	Obtained the following overall complexity (w.r.t. the length of the input n):
4.73/2.16	
4.73/2.16	   Complexity:  Nonterm
4.73/2.16	
4.73/2.16	   Cpx degree:  Nonterm
4.73/2.16	
4.73/2.16	   Solved cost: INF
4.73/2.16	
4.73/2.16	   Rule cost:   INF
4.73/2.16	
4.73/2.16	   Rule guard:  []
4.73/2.16	
4.73/2.16	
4.73/2.16	
4.73/2.16	NO
4.73/2.16	
4.73/2.16	
4.73/2.16	----------------------------------------
4.73/2.16	
4.73/2.16	(2)
4.73/2.16	BOUNDS(INF, INF)
4.90/2.19	EOF