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