5.66/2.50	WORST_CASE(NON_POLY, ?)
5.66/2.51	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
5.66/2.51	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.66/2.51	
5.66/2.51	
5.66/2.51	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
5.66/2.51	
5.66/2.51	(0) CpxIntTrs
5.66/2.51	(1) Loat Proof [FINISHED, 717 ms]
5.66/2.51	(2) BOUNDS(INF, INF)
5.66/2.51	
5.66/2.51	
5.66/2.51	----------------------------------------
5.66/2.51	
5.66/2.51	(0)
5.66/2.51	Obligation:
5.66/2.51	Complexity Int TRS consisting of the following rules:
5.66/2.51	f9(A, B) -> Com_1(f10(A, B)) :|: 5 >= A
5.66/2.51	f25(A, B) -> Com_1(f2(A, B)) :|: TRUE
5.66/2.51	f2(A, B) -> Com_1(f2(A, B)) :|: TRUE
5.66/2.51	f9(A, B) -> Com_1(f10(A, C)) :|: A >= 6 && 0 >= C + 1
5.66/2.51	f9(A, B) -> Com_1(f10(A, C)) :|: A >= 6 && C >= 1
5.66/2.51	f10(A, B) -> Com_1(f9(A + 1, B)) :|: A >= 6
5.66/2.51	f27(A, B) -> Com_1(f29(A, B)) :|: TRUE
5.66/2.51	f19(A, B) -> Com_1(f19(A - 1, B)) :|: A >= 3
5.66/2.51	f19(A, B) -> Com_1(f9(A, B)) :|: 2 >= A
5.66/2.51	f10(A, B) -> Com_1(f9(A + 1, B)) :|: 5 >= A
5.66/2.51	f9(A, B) -> Com_1(f19(A, 0)) :|: A >= 6
5.66/2.51	f0(A, B) -> Com_1(f9(C, B)) :|: TRUE
5.66/2.51	
5.66/2.51	The start-symbols are:[f0_2]
5.66/2.51	
5.66/2.51	
5.66/2.51	----------------------------------------
5.66/2.51	
5.66/2.51	(1) Loat Proof (FINISHED)
5.66/2.51	
5.66/2.51	
5.66/2.51	### Pre-processing the ITS problem ###
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Initial linear ITS problem
5.66/2.51	
5.66/2.51	   Start location: f0
5.66/2.51	
5.66/2.51	      0: f9 -> f10 : [ 5>=A ], cost: 1
5.66/2.51	
5.66/2.51	      3: f9 -> f10 : B'=free, [ A>=6 && 0>=1+free ], cost: 1
5.66/2.51	
5.66/2.51	      4: f9 -> f10 : B'=free_1, [ A>=6 && free_1>=1 ], cost: 1
5.66/2.51	
5.66/2.51	     10: f9 -> f19 : B'=0, [ A>=6 ], cost: 1
5.66/2.51	
5.66/2.51	      1: f25 -> f2 : [], cost: 1
5.66/2.51	
5.66/2.51	      2: f2 -> f2 : [], cost: 1
5.66/2.51	
5.66/2.51	      5: f10 -> f9 : A'=1+A, [ A>=6 ], cost: 1
5.66/2.51	
5.66/2.51	      9: f10 -> f9 : A'=1+A, [ 5>=A ], cost: 1
5.66/2.51	
5.66/2.51	      6: f27 -> f29 : [], cost: 1
5.66/2.51	
5.66/2.51	      7: f19 -> f19 : A'=-1+A, [ A>=3 ], cost: 1
5.66/2.51	
5.66/2.51	      8: f19 -> f9 : [ 2>=A ], cost: 1
5.66/2.51	
5.66/2.51	     11: f0 -> f9 : A'=free_2, [], cost: 1
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Removed unreachable and leaf rules:
5.66/2.51	
5.66/2.51	   Start location: f0
5.66/2.51	
5.66/2.51	      0: f9 -> f10 : [ 5>=A ], cost: 1
5.66/2.51	
5.66/2.51	      3: f9 -> f10 : B'=free, [ A>=6 && 0>=1+free ], cost: 1
5.66/2.51	
5.66/2.51	      4: f9 -> f10 : B'=free_1, [ A>=6 && free_1>=1 ], cost: 1
5.66/2.51	
5.66/2.51	     10: f9 -> f19 : B'=0, [ A>=6 ], cost: 1
5.66/2.51	
5.66/2.51	      5: f10 -> f9 : A'=1+A, [ A>=6 ], cost: 1
5.66/2.51	
5.66/2.51	      9: f10 -> f9 : A'=1+A, [ 5>=A ], cost: 1
5.66/2.51	
5.66/2.51	      7: f19 -> f19 : A'=-1+A, [ A>=3 ], cost: 1
5.66/2.51	
5.66/2.51	      8: f19 -> f9 : [ 2>=A ], cost: 1
5.66/2.51	
5.66/2.51	     11: f0 -> f9 : A'=free_2, [], cost: 1
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	### Simplification by acceleration and chaining ###
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Accelerating simple loops of location 5.
5.66/2.51	
5.66/2.51	   Accelerating the following rules:
5.66/2.51	
5.66/2.51	      7: f19 -> f19 : A'=-1+A, [ A>=3 ], cost: 1
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	   Accelerated rule 7 with metering function -2+A, yielding the new rule 12.
5.66/2.51	
5.66/2.51	   Removing the simple loops: 7.
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Accelerated all simple loops using metering functions (where possible):
5.66/2.51	
5.66/2.51	   Start location: f0
5.66/2.51	
5.66/2.51	      0: f9 -> f10 : [ 5>=A ], cost: 1
5.66/2.51	
5.66/2.51	      3: f9 -> f10 : B'=free, [ A>=6 && 0>=1+free ], cost: 1
5.66/2.51	
5.66/2.51	      4: f9 -> f10 : B'=free_1, [ A>=6 && free_1>=1 ], cost: 1
5.66/2.51	
5.66/2.51	     10: f9 -> f19 : B'=0, [ A>=6 ], cost: 1
5.66/2.51	
5.66/2.51	      5: f10 -> f9 : A'=1+A, [ A>=6 ], cost: 1
5.66/2.51	
5.66/2.51	      9: f10 -> f9 : A'=1+A, [ 5>=A ], cost: 1
5.66/2.51	
5.66/2.51	      8: f19 -> f9 : [ 2>=A ], cost: 1
5.66/2.51	
5.66/2.51	     12: f19 -> f19 : A'=2, [ A>=3 ], cost: -2+A
5.66/2.51	
5.66/2.51	     11: f0 -> f9 : A'=free_2, [], cost: 1
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Chained accelerated rules (with incoming rules):
5.66/2.51	
5.66/2.51	   Start location: f0
5.66/2.51	
5.66/2.51	      0: f9 -> f10 : [ 5>=A ], cost: 1
5.66/2.51	
5.66/2.51	      3: f9 -> f10 : B'=free, [ A>=6 && 0>=1+free ], cost: 1
5.66/2.51	
5.66/2.51	      4: f9 -> f10 : B'=free_1, [ A>=6 && free_1>=1 ], cost: 1
5.66/2.51	
5.66/2.51	     10: f9 -> f19 : B'=0, [ A>=6 ], cost: 1
5.66/2.51	
5.66/2.51	     13: f9 -> f19 : A'=2, B'=0, [ A>=6 ], cost: -1+A
5.66/2.51	
5.66/2.51	      5: f10 -> f9 : A'=1+A, [ A>=6 ], cost: 1
5.66/2.51	
5.66/2.51	      9: f10 -> f9 : A'=1+A, [ 5>=A ], cost: 1
5.66/2.51	
5.66/2.51	      8: f19 -> f9 : [ 2>=A ], cost: 1
5.66/2.51	
5.66/2.51	     11: f0 -> f9 : A'=free_2, [], cost: 1
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Eliminated locations (on tree-shaped paths):
5.66/2.51	
5.66/2.51	   Start location: f0
5.66/2.51	
5.66/2.51	     14: f9 -> f9 : A'=1+A, [ 5>=A ], cost: 2
5.66/2.51	
5.66/2.51	     15: f9 -> f9 : A'=1+A, B'=free, [ A>=6 && 0>=1+free ], cost: 2
5.66/2.51	
5.66/2.51	     16: f9 -> f9 : A'=1+A, B'=free_1, [ A>=6 && free_1>=1 ], cost: 2
5.66/2.51	
5.66/2.51	     17: f9 -> f9 : A'=2, B'=0, [ A>=6 ], cost: A
5.66/2.51	
5.66/2.51	     11: f0 -> f9 : A'=free_2, [], cost: 1
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Accelerating simple loops of location 0.
5.66/2.51	
5.66/2.51	   Accelerating the following rules:
5.66/2.51	
5.66/2.51	     14: f9 -> f9 : A'=1+A, [ 5>=A ], cost: 2
5.66/2.51	
5.66/2.51	     15: f9 -> f9 : A'=1+A, B'=free, [ A>=6 && 0>=1+free ], cost: 2
5.66/2.51	
5.66/2.51	     16: f9 -> f9 : A'=1+A, B'=free_1, [ A>=6 && free_1>=1 ], cost: 2
5.66/2.51	
5.66/2.51	     17: f9 -> f9 : A'=2, B'=0, [ A>=6 ], cost: A
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	   Accelerated rule 14 with metering function 6-A, yielding the new rule 18.
5.66/2.51	
5.66/2.51	   Accelerated rule 15 with NONTERM, yielding the new rule 19.
5.66/2.51	
5.66/2.51	   Accelerated rule 16 with NONTERM, yielding the new rule 20.
5.66/2.51	
5.66/2.51	   Found no metering function for rule 17.
5.66/2.51	
5.66/2.51	   Nested simple loops 17 (outer loop) and 18 (inner loop) with NONTERM, resulting in the new rules: 21, 22.
5.66/2.51	
5.66/2.51	   Removing the simple loops: 14 15 16 17.
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Accelerated all simple loops using metering functions (where possible):
5.66/2.51	
5.66/2.51	   Start location: f0
5.66/2.51	
5.66/2.51	     18: f9 -> f9 : A'=6, [ 5>=A ], cost: 12-2*A
5.66/2.51	
5.66/2.51	     19: f9 -> [9] : [ A>=6 && 0>=1+free ], cost: INF
5.66/2.51	
5.66/2.51	     20: f9 -> [9] : [ A>=6 && free_1>=1 ], cost: INF
5.66/2.51	
5.66/2.51	     21: f9 -> [9] : [ 5>=A && 18-2*A>=1 ], cost: INF
5.66/2.51	
5.66/2.51	     22: f9 -> [9] : A'=2, B'=0, [ A>=6 ], cost: INF
5.66/2.51	
5.66/2.51	     11: f0 -> f9 : A'=free_2, [], cost: 1
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Chained accelerated rules (with incoming rules):
5.66/2.51	
5.66/2.51	   Start location: f0
5.66/2.51	
5.66/2.51	     11: f0 -> f9 : A'=free_2, [], cost: 1
5.66/2.51	
5.66/2.51	     23: f0 -> f9 : A'=6, [ 5>=free_2 ], cost: 13-2*free_2
5.66/2.51	
5.66/2.51	     24: f0 -> [9] : A'=free_2, [ free_2>=6 ], cost: INF
5.66/2.51	
5.66/2.51	     25: f0 -> [9] : A'=free_2, [ free_2>=6 ], cost: INF
5.66/2.51	
5.66/2.51	     26: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: INF
5.66/2.51	
5.66/2.51	     27: f0 -> [9] : A'=2, B'=0, [], cost: INF
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Removed unreachable locations (and leaf rules with constant cost):
5.66/2.51	
5.66/2.51	   Start location: f0
5.66/2.51	
5.66/2.51	     23: f0 -> f9 : A'=6, [ 5>=free_2 ], cost: 13-2*free_2
5.66/2.51	
5.66/2.51	     24: f0 -> [9] : A'=free_2, [ free_2>=6 ], cost: INF
5.66/2.51	
5.66/2.51	     25: f0 -> [9] : A'=free_2, [ free_2>=6 ], cost: INF
5.66/2.51	
5.66/2.51	     26: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: INF
5.66/2.51	
5.66/2.51	     27: f0 -> [9] : A'=2, B'=0, [], cost: INF
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	### Computing asymptotic complexity ###
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Fully simplified ITS problem
5.66/2.51	
5.66/2.51	   Start location: f0
5.66/2.51	
5.66/2.51	     23: f0 -> f9 : A'=6, [ 5>=free_2 ], cost: 13-2*free_2
5.66/2.51	
5.66/2.51	     25: f0 -> [9] : A'=free_2, [ free_2>=6 ], cost: INF
5.66/2.51	
5.66/2.51	     26: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: INF
5.66/2.51	
5.66/2.51	     27: f0 -> [9] : A'=2, B'=0, [], cost: INF
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Computing asymptotic complexity for rule 23
5.66/2.51	
5.66/2.51	   Solved the limit problem by the following transformations:
5.66/2.51	
5.66/2.51	      Created initial limit problem:
5.66/2.51	
5.66/2.51	      6-free_2 (+/+!), 13-2*free_2 (+) [not solved]
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	      removing all constraints (solved by SMT)
5.66/2.51	
5.66/2.51	      resulting limit problem: [solved]
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	      applying transformation rule (C) using substitution {free_2==-n}
5.66/2.51	
5.66/2.51	      resulting limit problem:
5.66/2.51	
5.66/2.51	      [solved]
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	   Solution:
5.66/2.51	
5.66/2.51	      free_2 / -n
5.66/2.51	
5.66/2.51	   Resulting cost 13+2*n has complexity: Unbounded
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Found new complexity Unbounded.
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	Obtained the following overall complexity (w.r.t. the length of the input n):
5.66/2.51	
5.66/2.51	   Complexity:  Unbounded
5.66/2.51	
5.66/2.51	   Cpx degree:  Unbounded
5.66/2.51	
5.66/2.51	   Solved cost: 13+2*n
5.66/2.51	
5.66/2.51	   Rule cost:   13-2*free_2
5.66/2.51	
5.66/2.51	   Rule guard:  [ 5>=free_2 ]
5.66/2.51	
5.66/2.51	
5.66/2.51	
5.66/2.51	WORST_CASE(INF,?)
5.66/2.51	
5.66/2.51	
5.66/2.51	----------------------------------------
5.66/2.51	
5.66/2.51	(2)
5.66/2.51	BOUNDS(INF, INF)
5.91/2.53	EOF