4.09/2.02	WORST_CASE(NON_POLY, ?)
4.09/2.03	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.09/2.03	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.09/2.03	
4.09/2.03	
4.09/2.03	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
4.09/2.03	
4.09/2.03	(0) CpxIntTrs
4.09/2.03	(1) Loat Proof [FINISHED, 302 ms]
4.09/2.03	(2) BOUNDS(INF, INF)
4.09/2.03	
4.09/2.03	
4.09/2.03	----------------------------------------
4.09/2.03	
4.09/2.03	(0)
4.09/2.03	Obligation:
4.09/2.03	Complexity Int TRS consisting of the following rules:
4.09/2.03	f9(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f9(A, 1 + B, 1 + C, S, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= 1 + B && C >= 0
4.09/2.03	f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f0(A, B, C, D, E, F, S, G, V, W, X, L, M, N, O, P, Q, R)) :|: U >= T + 1 && E >= 1 && F >= 0
4.09/2.03	f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f5(A, B, C, D, 1 + E, -(1) + F, M, 0, W, X, K, M, N, V, S, E, Q, R)) :|: T >= U && E >= 0 && F >= 0 && H >= 0 && H <= 0
4.09/2.03	f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f12(A, B, C, D, E, F, G, 0, V, W, K, M, M, 0, O, E, S, R)) :|: X >= T && E >= 0 && F >= 0 && N >= 0 && N <= 0 && H >= 0 && H <= 0
4.09/2.03	f9(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f5(A, B, C, D, 1, T - 3 + C, S, 0, U, A1, K, S, V, X, W, P, D, -(2) + C)) :|: C >= 2 && B >= A && Y >= Z
4.09/2.03	f6(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f9(17, 1, 0, S, E, F, G, H, I, J, K, V, M, N, O, P, Q, R)) :|: TRUE
4.09/2.03	
4.09/2.03	The start-symbols are:[f6_18]
4.09/2.03	
4.09/2.03	
4.09/2.03	----------------------------------------
4.09/2.03	
4.09/2.03	(1) Loat Proof (FINISHED)
4.09/2.03	
4.09/2.03	
4.09/2.03	### Pre-processing the ITS problem ###
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Initial linear ITS problem
4.09/2.03	
4.09/2.03	   Start location: f6
4.09/2.03	
4.09/2.03	      0: f9 -> f9 : B'=1+B, C'=1+C, D'=free, [ A>=1+B && C>=0 ], cost: 1
4.09/2.03	
4.09/2.03	      4: f9 -> f5 : E'=1, F'=-3+free_22+C, G'=free_21, H'=0, Q'=free_24, J'=free_18, L'=free_25, M'=free_21, N'=free_19, O'=free_26, Q_1'=D, R'=-2+C, [ C>=2 && B>=A && free_20>=free_23 ], cost: 1
4.09/2.03	
4.09/2.03	      1: f5 -> f0 : A1'=B, B'=C, C'=D, D'=E, E'=F, F'=free_4, H'=free_3, Q'=free_5, J'=free_1, K'=L, L'=M, M'=N, N'=O, O'=P, P'=Q_1, Q_1'=R, [ free_6>=1+free_2 && E>=1 && F>=0 ], cost: 1
4.09/2.03	
4.09/2.03	      2: f5 -> f5 : E'=1+E, F'=-1+F, G'=L, H'=0, Q'=free_10, J'=free_9, L'=N, M'=L, N'=free_11, O'=free_7, P'=E, [ free_12>=free_8 && E>=0 && F>=0 && H==0 ], cost: 1
4.09/2.03	
4.09/2.03	      3: f5 -> f12 : A1'=B, B'=C, C'=D, D'=E, E'=F, F'=G, G'=0, H'=free_15, Q'=free_14, J'=K, K'=L, M'=0, N'=O, O'=E, P'=free_16, Q_1'=R, [ free_13>=free_17 && E>=0 && F>=0 && N==0 && H==0 ], cost: 1
4.09/2.03	
4.09/2.03	      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Removed unreachable and leaf rules:
4.09/2.03	
4.09/2.03	   Start location: f6
4.09/2.03	
4.09/2.03	      0: f9 -> f9 : B'=1+B, C'=1+C, D'=free, [ A>=1+B && C>=0 ], cost: 1
4.09/2.03	
4.09/2.03	      4: f9 -> f5 : E'=1, F'=-3+free_22+C, G'=free_21, H'=0, Q'=free_24, J'=free_18, L'=free_25, M'=free_21, N'=free_19, O'=free_26, Q_1'=D, R'=-2+C, [ C>=2 && B>=A && free_20>=free_23 ], cost: 1
4.09/2.03	
4.09/2.03	      2: f5 -> f5 : E'=1+E, F'=-1+F, G'=L, H'=0, Q'=free_10, J'=free_9, L'=N, M'=L, N'=free_11, O'=free_7, P'=E, [ free_12>=free_8 && E>=0 && F>=0 && H==0 ], cost: 1
4.09/2.03	
4.09/2.03	      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Simplified all rules, resulting in:
4.09/2.03	
4.09/2.03	   Start location: f6
4.09/2.03	
4.09/2.03	      0: f9 -> f9 : B'=1+B, C'=1+C, D'=free, [ A>=1+B && C>=0 ], cost: 1
4.09/2.03	
4.09/2.03	      4: f9 -> f5 : E'=1, F'=-3+free_22+C, G'=free_21, H'=0, Q'=free_24, J'=free_18, L'=free_25, M'=free_21, N'=free_19, O'=free_26, Q_1'=D, R'=-2+C, [ C>=2 && B>=A ], cost: 1
4.09/2.03	
4.09/2.03	      2: f5 -> f5 : E'=1+E, F'=-1+F, G'=L, H'=0, Q'=free_10, J'=free_9, L'=N, M'=L, N'=free_11, O'=free_7, P'=E, [ E>=0 && F>=0 && H==0 ], cost: 1
4.09/2.03	
4.09/2.03	      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	### Simplification by acceleration and chaining ###
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Accelerating simple loops of location 0.
4.09/2.03	
4.09/2.03	   Accelerating the following rules:
4.09/2.03	
4.09/2.03	      0: f9 -> f9 : B'=1+B, C'=1+C, D'=free, [ A>=1+B && C>=0 ], cost: 1
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	   Accelerated rule 0 with metering function -B+A, yielding the new rule 6.
4.09/2.03	
4.09/2.03	   Removing the simple loops: 0.
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Accelerating simple loops of location 1.
4.09/2.03	
4.09/2.03	   Accelerating the following rules:
4.09/2.03	
4.09/2.03	      2: f5 -> f5 : E'=1+E, F'=-1+F, G'=L, H'=0, Q'=free_10, J'=free_9, L'=N, M'=L, N'=free_11, O'=free_7, P'=E, [ E>=0 && F>=0 && H==0 ], cost: 1
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	   Accelerated rule 2 with metering function 1+F, yielding the new rule 7.
4.09/2.03	
4.09/2.03	   Removing the simple loops: 2.
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Accelerated all simple loops using metering functions (where possible):
4.09/2.03	
4.09/2.03	   Start location: f6
4.09/2.03	
4.09/2.03	      4: f9 -> f5 : E'=1, F'=-3+free_22+C, G'=free_21, H'=0, Q'=free_24, J'=free_18, L'=free_25, M'=free_21, N'=free_19, O'=free_26, Q_1'=D, R'=-2+C, [ C>=2 && B>=A ], cost: 1
4.09/2.03	
4.09/2.03	      6: f9 -> f9 : B'=A, C'=-B+C+A, D'=free, [ A>=1+B && C>=0 ], cost: -B+A
4.09/2.03	
4.09/2.03	      7: f5 -> f5 : E'=1+E+F, F'=-1, G'=free_11, H'=0, Q'=free_10, J'=free_9, L'=free_11, M'=free_11, N'=free_11, O'=free_7, P'=E+F, [ E>=0 && F>=0 && H==0 ], cost: 1+F
4.09/2.03	
4.09/2.03	      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Chained accelerated rules (with incoming rules):
4.09/2.03	
4.09/2.03	   Start location: f6
4.09/2.03	
4.09/2.03	      4: f9 -> f5 : E'=1, F'=-3+free_22+C, G'=free_21, H'=0, Q'=free_24, J'=free_18, L'=free_25, M'=free_21, N'=free_19, O'=free_26, Q_1'=D, R'=-2+C, [ C>=2 && B>=A ], cost: 1
4.09/2.03	
4.09/2.03	      9: f9 -> f5 : E'=-1+free_22+C, F'=-1, G'=free_11, H'=0, Q'=free_10, J'=free_9, L'=free_11, M'=free_11, N'=free_11, O'=free_7, P'=-2+free_22+C, Q_1'=D, R'=-2+C, [ C>=2 && B>=A && -3+free_22+C>=0 ], cost: -1+free_22+C
4.09/2.03	
4.09/2.03	      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1
4.09/2.03	
4.09/2.03	      8: f6 -> f9 : A'=17, B'=17, C'=16, D'=free, M'=free_27, [], cost: 17
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Removed unreachable locations (and leaf rules with constant cost):
4.09/2.03	
4.09/2.03	   Start location: f6
4.09/2.03	
4.09/2.03	      9: f9 -> f5 : E'=-1+free_22+C, F'=-1, G'=free_11, H'=0, Q'=free_10, J'=free_9, L'=free_11, M'=free_11, N'=free_11, O'=free_7, P'=-2+free_22+C, Q_1'=D, R'=-2+C, [ C>=2 && B>=A && -3+free_22+C>=0 ], cost: -1+free_22+C
4.09/2.03	
4.09/2.03	      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1
4.09/2.03	
4.09/2.03	      8: f6 -> f9 : A'=17, B'=17, C'=16, D'=free, M'=free_27, [], cost: 17
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Eliminated locations (on tree-shaped paths):
4.09/2.03	
4.09/2.03	   Start location: f6
4.09/2.03	
4.09/2.03	     10: f6 -> f5 : A'=17, B'=17, C'=16, D'=free, E'=15+free_22, F'=-1, G'=free_11, H'=0, Q'=free_10, J'=free_9, L'=free_11, M'=free_11, N'=free_11, O'=free_7, P'=14+free_22, Q_1'=free, R'=14, [ 13+free_22>=0 ], cost: 32+free_22
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	### Computing asymptotic complexity ###
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Fully simplified ITS problem
4.09/2.03	
4.09/2.03	   Start location: f6
4.09/2.03	
4.09/2.03	     10: f6 -> f5 : A'=17, B'=17, C'=16, D'=free, E'=15+free_22, F'=-1, G'=free_11, H'=0, Q'=free_10, J'=free_9, L'=free_11, M'=free_11, N'=free_11, O'=free_7, P'=14+free_22, Q_1'=free, R'=14, [ 13+free_22>=0 ], cost: 32+free_22
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Computing asymptotic complexity for rule 10
4.09/2.03	
4.09/2.03	   Solved the limit problem by the following transformations:
4.09/2.03	
4.09/2.03	      Created initial limit problem:
4.09/2.03	
4.09/2.03	      32+free_22 (+), 14+free_22 (+/+!) [not solved]
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	      removing all constraints (solved by SMT)
4.09/2.03	
4.09/2.03	      resulting limit problem: [solved]
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	      applying transformation rule (C) using substitution {free_22==n}
4.09/2.03	
4.09/2.03	      resulting limit problem:
4.09/2.03	
4.09/2.03	      [solved]
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	   Solution:
4.09/2.03	
4.09/2.03	      free_22 / n
4.09/2.03	
4.09/2.03	   Resulting cost 32+n has complexity: Unbounded
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Found new complexity Unbounded.
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	Obtained the following overall complexity (w.r.t. the length of the input n):
4.09/2.03	
4.09/2.03	   Complexity:  Unbounded
4.09/2.03	
4.09/2.03	   Cpx degree:  Unbounded
4.09/2.03	
4.09/2.03	   Solved cost: 32+n
4.09/2.03	
4.09/2.03	   Rule cost:   32+free_22
4.09/2.03	
4.09/2.03	   Rule guard:  [ 13+free_22>=0 ]
4.09/2.03	
4.09/2.03	
4.09/2.03	
4.09/2.03	WORST_CASE(INF,?)
4.09/2.03	
4.09/2.03	
4.09/2.03	----------------------------------------
4.09/2.03	
4.09/2.03	(2)
4.09/2.03	BOUNDS(INF, INF)
4.09/2.04	EOF