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