4.38/2.03	WORST_CASE(NON_POLY, ?)
4.38/2.03	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.38/2.03	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.38/2.03	
4.38/2.03	
4.38/2.03	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
4.38/2.03	
4.38/2.03	(0) CpxIntTrs
4.38/2.03	(1) Loat Proof [FINISHED, 311 ms]
4.38/2.03	(2) BOUNDS(INF, INF)
4.38/2.03	
4.38/2.03	
4.38/2.03	----------------------------------------
4.38/2.03	
4.38/2.03	(0)
4.38/2.03	Obligation:
4.38/2.03	Complexity Int TRS consisting of the following rules:
4.38/2.03	f0(A, B, C, D, E, F, G) -> Com_1(f2(A, B, C, D, E, F, G)) :|: 0 >= A
4.38/2.03	f0(A, B, C, D, E, F, G) -> Com_1(f0(-(1) + A, C, -(1) + C, A, E, F, G)) :|: A >= 1
4.38/2.03	f1(A, B, C, D, E, F, G) -> Com_1(f0(-(1) + A, B, -(1) + C, D, C, A, G)) :|: A >= 1 && C >= 1
4.38/2.03	f2(A, B, C, D, E, F, G) -> Com_1(f4(A, B, C, D, E, F, H)) :|: 0 >= C
4.38/2.03	f2(A, B, C, D, E, F, G) -> Com_1(f0(H, B, C, D, E, F, G)) :|: H >= 1 && C >= 1
4.38/2.03	f3(A, B, C, D, E, F, G) -> Com_1(f2(H, B, I, D, E, F, G)) :|: TRUE
4.38/2.03	
4.38/2.03	The start-symbols are:[f3_7]
4.38/2.03	
4.38/2.03	
4.38/2.03	----------------------------------------
4.38/2.03	
4.38/2.03	(1) Loat Proof (FINISHED)
4.38/2.03	
4.38/2.03	
4.38/2.03	### Pre-processing the ITS problem ###
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Initial linear ITS problem
4.38/2.03	
4.38/2.03	   Start location: f3
4.38/2.03	
4.38/2.03	      0: f0 -> f2 : [ 0>=A ], cost: 1
4.38/2.03	
4.38/2.03	      1: f0 -> f0 : A'=-1+A, B'=C, C'=-1+C, D'=A, [ A>=1 ], cost: 1
4.38/2.03	
4.38/2.03	      2: f1 -> f0 : A'=-1+A, C'=-1+C, E'=C, F'=A, [ A>=1 && C>=1 ], cost: 1
4.38/2.03	
4.38/2.03	      3: f2 -> f4 : G'=free, [ 0>=C ], cost: 1
4.38/2.03	
4.38/2.03	      4: f2 -> f0 : A'=free_1, [ free_1>=1 && C>=1 ], cost: 1
4.38/2.03	
4.38/2.03	      5: f3 -> f2 : A'=free_3, C'=free_2, [], cost: 1
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Removed unreachable and leaf rules:
4.38/2.03	
4.38/2.03	   Start location: f3
4.38/2.03	
4.38/2.03	      0: f0 -> f2 : [ 0>=A ], cost: 1
4.38/2.03	
4.38/2.03	      1: f0 -> f0 : A'=-1+A, B'=C, C'=-1+C, D'=A, [ A>=1 ], cost: 1
4.38/2.03	
4.38/2.03	      4: f2 -> f0 : A'=free_1, [ free_1>=1 && C>=1 ], cost: 1
4.38/2.03	
4.38/2.03	      5: f3 -> f2 : A'=free_3, C'=free_2, [], cost: 1
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	### Simplification by acceleration and chaining ###
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Accelerating simple loops of location 0.
4.38/2.03	
4.38/2.03	   Accelerating the following rules:
4.38/2.03	
4.38/2.03	      1: f0 -> f0 : A'=-1+A, B'=C, C'=-1+C, D'=A, [ A>=1 ], cost: 1
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	   Accelerated rule 1 with metering function A, yielding the new rule 6.
4.38/2.03	
4.38/2.03	   Removing the simple loops: 1.
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Accelerated all simple loops using metering functions (where possible):
4.38/2.03	
4.38/2.03	   Start location: f3
4.38/2.03	
4.38/2.03	      0: f0 -> f2 : [ 0>=A ], cost: 1
4.38/2.03	
4.38/2.03	      6: f0 -> f0 : A'=0, B'=1+C-A, C'=C-A, D'=1, [ A>=1 ], cost: A
4.38/2.03	
4.38/2.03	      4: f2 -> f0 : A'=free_1, [ free_1>=1 && C>=1 ], cost: 1
4.38/2.03	
4.38/2.03	      5: f3 -> f2 : A'=free_3, C'=free_2, [], cost: 1
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Chained accelerated rules (with incoming rules):
4.38/2.03	
4.38/2.03	   Start location: f3
4.38/2.03	
4.38/2.03	      0: f0 -> f2 : [ 0>=A ], cost: 1
4.38/2.03	
4.38/2.03	      4: f2 -> f0 : A'=free_1, [ free_1>=1 && C>=1 ], cost: 1
4.38/2.03	
4.38/2.03	      7: f2 -> f0 : A'=0, B'=1+C-free_1, C'=C-free_1, D'=1, [ free_1>=1 && C>=1 ], cost: 1+free_1
4.38/2.03	
4.38/2.03	      5: f3 -> f2 : A'=free_3, C'=free_2, [], cost: 1
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Eliminated locations (on tree-shaped paths):
4.38/2.03	
4.38/2.03	   Start location: f3
4.38/2.03	
4.38/2.03	      8: f2 -> f2 : A'=0, B'=1+C-free_1, C'=C-free_1, D'=1, [ free_1>=1 && C>=1 ], cost: 2+free_1
4.38/2.03	
4.38/2.03	      5: f3 -> f2 : A'=free_3, C'=free_2, [], cost: 1
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Accelerating simple loops of location 2.
4.38/2.03	
4.38/2.03	   Accelerating the following rules:
4.38/2.03	
4.38/2.03	      8: f2 -> f2 : A'=0, B'=1+C-free_1, C'=C-free_1, D'=1, [ free_1>=1 && C>=1 ], cost: 2+free_1
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	      During metering: Instantiating temporary variables by {free_1==1}
4.38/2.03	
4.38/2.03	   Accelerated rule 8 with metering function C, yielding the new rule 9.
4.38/2.03	
4.38/2.03	   Removing the simple loops: 8.
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Accelerated all simple loops using metering functions (where possible):
4.38/2.03	
4.38/2.03	   Start location: f3
4.38/2.03	
4.38/2.03	      9: f2 -> f2 : A'=0, B'=1, C'=0, D'=1, [ C>=1 ], cost: 3*C
4.38/2.03	
4.38/2.03	      5: f3 -> f2 : A'=free_3, C'=free_2, [], cost: 1
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Chained accelerated rules (with incoming rules):
4.38/2.03	
4.38/2.03	   Start location: f3
4.38/2.03	
4.38/2.03	      5: f3 -> f2 : A'=free_3, C'=free_2, [], cost: 1
4.38/2.03	
4.38/2.03	     10: f3 -> f2 : A'=0, B'=1, C'=0, D'=1, [ free_2>=1 ], cost: 1+3*free_2
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Removed unreachable locations (and leaf rules with constant cost):
4.38/2.03	
4.38/2.03	   Start location: f3
4.38/2.03	
4.38/2.03	     10: f3 -> f2 : A'=0, B'=1, C'=0, D'=1, [ free_2>=1 ], cost: 1+3*free_2
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	### Computing asymptotic complexity ###
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Fully simplified ITS problem
4.38/2.03	
4.38/2.03	   Start location: f3
4.38/2.03	
4.38/2.03	     10: f3 -> f2 : A'=0, B'=1, C'=0, D'=1, [ free_2>=1 ], cost: 1+3*free_2
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Computing asymptotic complexity for rule 10
4.38/2.03	
4.38/2.03	   Solved the limit problem by the following transformations:
4.38/2.03	
4.38/2.03	      Created initial limit problem:
4.38/2.03	
4.38/2.03	      free_2 (+/+!), 1+3*free_2 (+) [not solved]
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	      removing all constraints (solved by SMT)
4.38/2.03	
4.38/2.03	      resulting limit problem: [solved]
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	      applying transformation rule (C) using substitution {free_2==n}
4.38/2.03	
4.38/2.03	      resulting limit problem:
4.38/2.03	
4.38/2.03	      [solved]
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	   Solution:
4.38/2.03	
4.38/2.03	      free_2 / n
4.38/2.03	
4.38/2.03	   Resulting cost 1+3*n has complexity: Unbounded
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Found new complexity Unbounded.
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	Obtained the following overall complexity (w.r.t. the length of the input n):
4.38/2.03	
4.38/2.03	   Complexity:  Unbounded
4.38/2.03	
4.38/2.03	   Cpx degree:  Unbounded
4.38/2.03	
4.38/2.03	   Solved cost: 1+3*n
4.38/2.03	
4.38/2.03	   Rule cost:   1+3*free_2
4.38/2.03	
4.38/2.03	   Rule guard:  [ free_2>=1 ]
4.38/2.03	
4.38/2.03	
4.38/2.03	
4.38/2.03	WORST_CASE(INF,?)
4.38/2.03	
4.38/2.03	
4.38/2.03	----------------------------------------
4.38/2.03	
4.38/2.03	(2)
4.38/2.03	BOUNDS(INF, INF)
4.38/2.05	EOF