3.69/1.87	WORST_CASE(NON_POLY, ?)
3.69/1.87	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
3.69/1.87	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.69/1.87	
3.69/1.87	
3.69/1.87	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
3.69/1.87	
3.69/1.87	(0) CpxIntTrs
3.69/1.87	(1) Loat Proof [FINISHED, 182 ms]
3.69/1.87	(2) BOUNDS(INF, INF)
3.69/1.87	
3.69/1.87	
3.69/1.87	----------------------------------------
3.69/1.87	
3.69/1.87	(0)
3.69/1.87	Obligation:
3.69/1.87	Complexity Int TRS consisting of the following rules:
3.69/1.87	f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(f1(A, 1 + B, D, Q, D, R, B, H, I, J, K, L, M, N, O, P)) :|: A >= B + 1 && B >= 0
3.69/1.87	f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(f4(R, S, U, X, W, F, G, Q, T, V, Y, Z, C, N, O, P)) :|: B >= A && B >= 0 && S >= Q && Q >= 2
3.69/1.87	f3(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(f4(T, V, S, Y, X, F, G, R, U, W, Z, B1, O, Q, O, P)) :|: 0 >= R && 0 >= A1
3.69/1.87	f3(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(f1(R, 2, U, S, U, F, G, R, T, U, K, L, M, Q, T, V)) :|: R >= 2
3.69/1.87	f3(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(f4(R, S, U, Y, X, F, G, 1, T, W, Z, B1, D, Q, V, P)) :|: TRUE
3.69/1.87	
3.69/1.87	The start-symbols are:[f3_16]
3.69/1.87	
3.69/1.87	
3.69/1.87	----------------------------------------
3.69/1.87	
3.69/1.87	(1) Loat Proof (FINISHED)
3.69/1.87	
3.69/1.87	
3.69/1.87	### Pre-processing the ITS problem ###
3.69/1.87	
3.69/1.87	
3.69/1.87	
3.69/1.87	Initial linear ITS problem
3.69/1.87	
3.69/1.87	   Start location: f3
3.69/1.87	
3.69/1.87	      0: f1 -> f1 : B'=1+B, C'=D, D'=free, E'=D, F'=free_1, G'=B, [ A>=1+B && B>=0 ], cost: 1
3.69/1.87	
3.69/1.87	      1: f1 -> f4 : A'=free_5, A1'=free_8, B'=free_4, B1'=free_7, C'=free_10, D'=F, E'=G, F'=free_11, G'=free_3, H'=free_6, Q'=free_9, J'=free_2, K'=C, L'=N, M'=O, N'=P, [ B>=A && B>=0 && free_8>=free_11 && free_11>=2 ], cost: 1
3.69/1.87	
3.69/1.87	      2: f3 -> f4 : A'=free_15, A1'=free_18, B'=free_14, B1'=free_17, C'=free_21, D'=F, E'=G, F'=free_22, G'=free_13, H'=free_16, Q'=free_20, J'=free_12, K'=N, L'=N, M'=free_19, N'=P, [ 0>=free_22 && 0>=free_23 ], cost: 1
3.69/1.87	
3.69/1.87	      3: f3 -> f1 : A'=free_25, B'=2, C'=free_27, D'=free_24, E'=free_27, H'=free_25, Q'=free_26, J'=free_27, N'=free_26, O'=free_28, P'=free_29, [ free_25>=2 ], cost: 1
3.69/1.87	
3.69/1.87	      4: f3 -> f4 : A'=free_33, A1'=free_36, B'=free_32, B1'=free_35, C'=free_39, D'=F, E'=G, F'=1, G'=free_40, H'=free_31, Q'=free_34, J'=free_38, K'=D, L'=free_37, M'=free_30, N'=P, [], cost: 1
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	Removed unreachable and leaf rules:
3.69/1.88	
3.69/1.88	   Start location: f3
3.69/1.88	
3.69/1.88	      0: f1 -> f1 : B'=1+B, C'=D, D'=free, E'=D, F'=free_1, G'=B, [ A>=1+B && B>=0 ], cost: 1
3.69/1.88	
3.69/1.88	      3: f3 -> f1 : A'=free_25, B'=2, C'=free_27, D'=free_24, E'=free_27, H'=free_25, Q'=free_26, J'=free_27, N'=free_26, O'=free_28, P'=free_29, [ free_25>=2 ], cost: 1
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	### Simplification by acceleration and chaining ###
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	Accelerating simple loops of location 0.
3.69/1.88	
3.69/1.88	   Accelerating the following rules:
3.69/1.88	
3.69/1.88	      0: f1 -> f1 : B'=1+B, C'=D, D'=free, E'=D, F'=free_1, G'=B, [ A>=1+B && B>=0 ], cost: 1
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	   Accelerated rule 0 with metering function -B+A, yielding the new rule 5.
3.69/1.88	
3.69/1.88	   Removing the simple loops: 0.
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	Accelerated all simple loops using metering functions (where possible):
3.69/1.88	
3.69/1.88	   Start location: f3
3.69/1.88	
3.69/1.88	      5: f1 -> f1 : B'=A, C'=free, D'=free, E'=free, F'=free_1, G'=-1+A, [ A>=1+B && B>=0 ], cost: -B+A
3.69/1.88	
3.69/1.88	      3: f3 -> f1 : A'=free_25, B'=2, C'=free_27, D'=free_24, E'=free_27, H'=free_25, Q'=free_26, J'=free_27, N'=free_26, O'=free_28, P'=free_29, [ free_25>=2 ], cost: 1
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	Chained accelerated rules (with incoming rules):
3.69/1.88	
3.69/1.88	   Start location: f3
3.69/1.88	
3.69/1.88	      3: f3 -> f1 : A'=free_25, B'=2, C'=free_27, D'=free_24, E'=free_27, H'=free_25, Q'=free_26, J'=free_27, N'=free_26, O'=free_28, P'=free_29, [ free_25>=2 ], cost: 1
3.69/1.88	
3.69/1.88	      6: f3 -> f1 : A'=free_25, B'=free_25, C'=free, D'=free, E'=free, F'=free_1, G'=-1+free_25, H'=free_25, Q'=free_26, J'=free_27, N'=free_26, O'=free_28, P'=free_29, [ free_25>=3 ], cost: -1+free_25
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	Removed unreachable locations (and leaf rules with constant cost):
3.69/1.88	
3.69/1.88	   Start location: f3
3.69/1.88	
3.69/1.88	      6: f3 -> f1 : A'=free_25, B'=free_25, C'=free, D'=free, E'=free, F'=free_1, G'=-1+free_25, H'=free_25, Q'=free_26, J'=free_27, N'=free_26, O'=free_28, P'=free_29, [ free_25>=3 ], cost: -1+free_25
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	### Computing asymptotic complexity ###
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	Fully simplified ITS problem
3.69/1.88	
3.69/1.88	   Start location: f3
3.69/1.88	
3.69/1.88	      6: f3 -> f1 : A'=free_25, B'=free_25, C'=free, D'=free, E'=free, F'=free_1, G'=-1+free_25, H'=free_25, Q'=free_26, J'=free_27, N'=free_26, O'=free_28, P'=free_29, [ free_25>=3 ], cost: -1+free_25
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	Computing asymptotic complexity for rule 6
3.69/1.88	
3.69/1.88	   Solved the limit problem by the following transformations:
3.69/1.88	
3.69/1.88	      Created initial limit problem:
3.69/1.88	
3.69/1.88	      -2+free_25 (+/+!), -1+free_25 (+) [not solved]
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	      removing all constraints (solved by SMT)
3.69/1.88	
3.69/1.88	      resulting limit problem: [solved]
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	      applying transformation rule (C) using substitution {free_25==n}
3.69/1.88	
3.69/1.88	      resulting limit problem:
3.69/1.88	
3.69/1.88	      [solved]
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	   Solution:
3.69/1.88	
3.69/1.88	      free_25 / n
3.69/1.88	
3.69/1.88	   Resulting cost -1+n has complexity: Unbounded
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	Found new complexity Unbounded.
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	Obtained the following overall complexity (w.r.t. the length of the input n):
3.69/1.88	
3.69/1.88	   Complexity:  Unbounded
3.69/1.88	
3.69/1.88	   Cpx degree:  Unbounded
3.69/1.88	
3.69/1.88	   Solved cost: -1+n
3.69/1.88	
3.69/1.88	   Rule cost:   -1+free_25
3.69/1.88	
3.69/1.88	   Rule guard:  [ free_25>=3 ]
3.69/1.88	
3.69/1.88	
3.69/1.88	
3.69/1.88	WORST_CASE(INF,?)
3.69/1.88	
3.69/1.88	
3.69/1.88	----------------------------------------
3.69/1.88	
3.69/1.88	(2)
3.69/1.88	BOUNDS(INF, INF)
3.69/1.89	EOF