5.35/2.59	WORST_CASE(NON_POLY, ?)
5.35/2.60	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
5.35/2.60	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.35/2.60	
5.35/2.60	
5.35/2.60	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
5.35/2.60	
5.35/2.60	(0) CpxIntTrs
5.35/2.60	(1) Loat Proof [FINISHED, 817 ms]
5.35/2.60	(2) BOUNDS(INF, INF)
5.35/2.60	
5.35/2.60	
5.35/2.60	----------------------------------------
5.35/2.60	
5.35/2.60	(0)
5.35/2.60	Obligation:
5.35/2.60	Complexity Int TRS consisting of the following rules:
5.35/2.60	f3(A, B, C) -> Com_1(f2(A, B, C)) :|: TRUE
5.35/2.60	f2(A, B, C) -> Com_1(f2(-(1) + E, B, C)) :|: 0 >= A + 1 && 0 >= D && B >= 1
5.35/2.60	f2(A, B, C) -> Com_1(f2(-(1) + E, B, C)) :|: 0 >= A + 1 && 0 >= D && 0 >= B
5.35/2.60	f2(A, B, C) -> Com_1(f2(1 + E, B, C)) :|: D >= 2 && 0 >= A + 1
5.35/2.60	f2(A, B, C) -> Com_1(f2(-(1) + E, B, C)) :|: A >= 1 && 0 >= 2 + D && B >= 1
5.35/2.60	f2(A, B, C) -> Com_1(f2(-(1) + E, B, C)) :|: A >= 1 && 0 >= 2 + D && 0 >= B
5.35/2.60	f2(A, B, C) -> Com_1(f2(1 + E, B, C)) :|: D >= 0 && A >= 1
5.35/2.60	f2(A, B, C) -> Com_1(f300(0, B, E)) :|: 0 >= A + 1
5.35/2.60	f2(A, B, C) -> Com_1(f300(0, B, E)) :|: A >= 1
5.35/2.60	f2(A, B, C) -> Com_1(f300(A, B, E)) :|: A >= 0 && A <= 0
5.35/2.60	
5.35/2.60	The start-symbols are:[f3_3]
5.35/2.60	
5.35/2.60	
5.35/2.60	----------------------------------------
5.35/2.60	
5.35/2.60	(1) Loat Proof (FINISHED)
5.35/2.60	
5.35/2.60	
5.35/2.60	### Pre-processing the ITS problem ###
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Initial linear ITS problem
5.35/2.60	
5.35/2.60	   Start location: f3
5.35/2.60	
5.35/2.60	      0: f3 -> f2 : [], cost: 1
5.35/2.60	
5.35/2.60	      1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && 0>=free && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=free_2 && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      3: f2 -> f2 : A'=1+free_5, [ free_4>=2 && 0>=1+A ], cost: 1
5.35/2.60	
5.35/2.60	      4: f2 -> f2 : A'=-1+free_7, [ A>=1 && 0>=2+free_6 && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=2+free_8 && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      6: f2 -> f2 : A'=1+free_11, [ free_10>=0 && A>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      7: f2 -> f300 : A'=0, C'=free_12, [ 0>=1+A ], cost: 1
5.35/2.60	
5.35/2.60	      8: f2 -> f300 : A'=0, C'=free_13, [ A>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      9: f2 -> f300 : C'=free_14, [ A==0 ], cost: 1
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Removed unreachable and leaf rules:
5.35/2.60	
5.35/2.60	   Start location: f3
5.35/2.60	
5.35/2.60	      0: f3 -> f2 : [], cost: 1
5.35/2.60	
5.35/2.60	      1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && 0>=free && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=free_2 && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      3: f2 -> f2 : A'=1+free_5, [ free_4>=2 && 0>=1+A ], cost: 1
5.35/2.60	
5.35/2.60	      4: f2 -> f2 : A'=-1+free_7, [ A>=1 && 0>=2+free_6 && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=2+free_8 && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      6: f2 -> f2 : A'=1+free_11, [ free_10>=0 && A>=1 ], cost: 1
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Simplified all rules, resulting in:
5.35/2.60	
5.35/2.60	   Start location: f3
5.35/2.60	
5.35/2.60	      0: f3 -> f2 : [], cost: 1
5.35/2.60	
5.35/2.60	      1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      3: f2 -> f2 : A'=1+free_5, [ 0>=1+A ], cost: 1
5.35/2.60	
5.35/2.60	      4: f2 -> f2 : A'=-1+free_7, [ A>=1 && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      6: f2 -> f2 : A'=1+free_11, [ A>=1 ], cost: 1
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	### Simplification by acceleration and chaining ###
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Accelerating simple loops of location 1.
5.35/2.60	
5.35/2.60	   Accelerating the following rules:
5.35/2.60	
5.35/2.60	      1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      3: f2 -> f2 : A'=1+free_5, [ 0>=1+A ], cost: 1
5.35/2.60	
5.35/2.60	      4: f2 -> f2 : A'=-1+free_7, [ A>=1 && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      6: f2 -> f2 : A'=1+free_11, [ A>=1 ], cost: 1
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	   Accelerated rule 1 with NONTERM (after strengthening guard), yielding the new rule 10.
5.35/2.60	
5.35/2.60	   Accelerated rule 2 with NONTERM (after strengthening guard), yielding the new rule 11.
5.35/2.60	
5.35/2.60	   Accelerated rule 3 with NONTERM (after strengthening guard), yielding the new rule 12.
5.35/2.60	
5.35/2.60	   Accelerated rule 4 with NONTERM (after strengthening guard), yielding the new rule 13.
5.35/2.60	
5.35/2.60	   Accelerated rule 5 with NONTERM (after strengthening guard), yielding the new rule 14.
5.35/2.60	
5.35/2.60	   Accelerated rule 6 with NONTERM (after strengthening guard), yielding the new rule 15.
5.35/2.60	
5.35/2.60	   Removing the simple loops:.
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Accelerated all simple loops using metering functions (where possible):
5.35/2.60	
5.35/2.60	   Start location: f3
5.35/2.60	
5.35/2.60	      0: f3 -> f2 : [], cost: 1
5.35/2.60	
5.35/2.60	      1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      3: f2 -> f2 : A'=1+free_5, [ 0>=1+A ], cost: 1
5.35/2.60	
5.35/2.60	      4: f2 -> f2 : A'=-1+free_7, [ A>=1 && B>=1 ], cost: 1
5.35/2.60	
5.35/2.60	      5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=B ], cost: 1
5.35/2.60	
5.35/2.60	      6: f2 -> f2 : A'=1+free_11, [ A>=1 ], cost: 1
5.35/2.60	
5.35/2.60	     10: f2 -> [3] : [ 0>=1+A && B>=1 && 0>=free_1 ], cost: INF
5.35/2.60	
5.35/2.60	     11: f2 -> [3] : [ 0>=1+A && 0>=B && 0>=free_3 ], cost: INF
5.35/2.60	
5.35/2.60	     12: f2 -> [3] : [ 0>=1+A && 0>=2+free_5 ], cost: INF
5.35/2.60	
5.35/2.60	     13: f2 -> [3] : [ A>=1 && B>=1 && -1+free_7>=1 ], cost: INF
5.35/2.60	
5.35/2.60	     14: f2 -> [3] : [ A>=1 && 0>=B && -1+free_9>=1 ], cost: INF
5.35/2.60	
5.35/2.60	     15: f2 -> [3] : [ A>=1 && 1+free_11>=1 ], cost: INF
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Chained accelerated rules (with incoming rules):
5.35/2.60	
5.35/2.60	   Start location: f3
5.35/2.60	
5.35/2.60	      0: f3 -> f2 : [], cost: 1
5.35/2.60	
5.35/2.60	     16: f3 -> f2 : A'=-1+free_1, [ 0>=1+A && B>=1 ], cost: 2
5.35/2.60	
5.35/2.60	     17: f3 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=B ], cost: 2
5.35/2.60	
5.35/2.60	     18: f3 -> f2 : A'=1+free_5, [ 0>=1+A ], cost: 2
5.35/2.60	
5.35/2.60	     19: f3 -> f2 : A'=-1+free_7, [ A>=1 && B>=1 ], cost: 2
5.35/2.60	
5.35/2.60	     20: f3 -> f2 : A'=-1+free_9, [ A>=1 && 0>=B ], cost: 2
5.35/2.60	
5.35/2.60	     21: f3 -> f2 : A'=1+free_11, [ A>=1 ], cost: 2
5.35/2.60	
5.35/2.60	     22: f3 -> [3] : [ 0>=1+A && B>=1 ], cost: INF
5.35/2.60	
5.35/2.60	     23: f3 -> [3] : [ 0>=1+A && 0>=B ], cost: INF
5.35/2.60	
5.35/2.60	     24: f3 -> [3] : [ 0>=1+A ], cost: INF
5.35/2.60	
5.35/2.60	     25: f3 -> [3] : [ A>=1 && B>=1 ], cost: INF
5.35/2.60	
5.35/2.60	     26: f3 -> [3] : [ A>=1 && 0>=B ], cost: INF
5.35/2.60	
5.35/2.60	     27: f3 -> [3] : [ A>=1 ], cost: INF
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Removed unreachable locations (and leaf rules with constant cost):
5.35/2.60	
5.35/2.60	   Start location: f3
5.35/2.60	
5.35/2.60	     22: f3 -> [3] : [ 0>=1+A && B>=1 ], cost: INF
5.35/2.60	
5.35/2.60	     23: f3 -> [3] : [ 0>=1+A && 0>=B ], cost: INF
5.35/2.60	
5.35/2.60	     24: f3 -> [3] : [ 0>=1+A ], cost: INF
5.35/2.60	
5.35/2.60	     25: f3 -> [3] : [ A>=1 && B>=1 ], cost: INF
5.35/2.60	
5.35/2.60	     26: f3 -> [3] : [ A>=1 && 0>=B ], cost: INF
5.35/2.60	
5.35/2.60	     27: f3 -> [3] : [ A>=1 ], cost: INF
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	### Computing asymptotic complexity ###
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Fully simplified ITS problem
5.35/2.60	
5.35/2.60	   Start location: f3
5.35/2.60	
5.35/2.60	     22: f3 -> [3] : [ 0>=1+A && B>=1 ], cost: INF
5.35/2.60	
5.35/2.60	     23: f3 -> [3] : [ 0>=1+A && 0>=B ], cost: INF
5.35/2.60	
5.35/2.60	     24: f3 -> [3] : [ 0>=1+A ], cost: INF
5.35/2.60	
5.35/2.60	     25: f3 -> [3] : [ A>=1 && B>=1 ], cost: INF
5.35/2.60	
5.35/2.60	     26: f3 -> [3] : [ A>=1 && 0>=B ], cost: INF
5.35/2.60	
5.35/2.60	     27: f3 -> [3] : [ A>=1 ], cost: INF
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Computing asymptotic complexity for rule 22
5.35/2.60	
5.35/2.60	   Resulting cost INF has complexity: Nonterm
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Found new complexity Nonterm.
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	Obtained the following overall complexity (w.r.t. the length of the input n):
5.35/2.60	
5.35/2.60	   Complexity:  Nonterm
5.35/2.60	
5.35/2.60	   Cpx degree:  Nonterm
5.35/2.60	
5.35/2.60	   Solved cost: INF
5.35/2.60	
5.35/2.60	   Rule cost:   INF
5.35/2.60	
5.35/2.60	   Rule guard:  [ 0>=1+A && B>=1 ]
5.35/2.60	
5.35/2.60	
5.35/2.60	
5.35/2.60	NO
5.35/2.60	
5.35/2.60	
5.35/2.60	----------------------------------------
5.35/2.60	
5.35/2.60	(2)
5.35/2.60	BOUNDS(INF, INF)
5.35/2.61	EOF