4.01/1.92	WORST_CASE(NON_POLY, ?)
4.01/1.93	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.01/1.93	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.01/1.93	
4.01/1.93	
4.01/1.93	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
4.01/1.93	
4.01/1.93	(0) CpxIntTrs
4.01/1.93	(1) Loat Proof [FINISHED, 215 ms]
4.01/1.93	(2) BOUNDS(INF, INF)
4.01/1.93	
4.01/1.93	
4.01/1.93	----------------------------------------
4.01/1.93	
4.01/1.93	(0)
4.01/1.93	Obligation:
4.01/1.93	Complexity Int TRS consisting of the following rules:
4.01/1.93	f0(A, B, C, D) -> Com_1(f10001(A, B, C, D)) :|: TRUE
4.01/1.93	f2(A, B, C, D) -> Com_1(f2(A, B, C, D)) :|: TRUE
4.01/1.93	f2(A, B, C, D) -> Com_1(f10001(A, B, C, D)) :|: TRUE
4.01/1.93	f2(A, B, C, D) -> Com_1(f1200(B, B, C, D)) :|: TRUE
4.01/1.93	f2200(A, B, C, D) -> Com_1(f10000(A, B, 0, D)) :|: C >= 0 && C <= 0
4.01/1.93	f12(A, B, C, D) -> Com_1(f12(A, B, C, D)) :|: TRUE
4.01/1.93	f100(A, B, C, D) -> Com_1(f110(A, 1, C, D)) :|: TRUE
4.01/1.93	f110(A, B, C, D) -> Com_1(f120(A, 2, C, D)) :|: TRUE
4.01/1.93	f120(A, B, C, D) -> Com_1(f120(A, B, C, D)) :|: TRUE
4.01/1.93	f1200(A, B, C, D) -> Com_1(f1200(A, B, C, D)) :|: TRUE
4.01/1.93	f0(A, B, C, D) -> Com_1(f2(A, 2, C, D)) :|: TRUE
4.01/1.93	f0(A, B, C, D) -> Com_1(f10001(A, 1, C, D)) :|: TRUE
4.01/1.93	f0(A, B, C, D) -> Com_1(f110(1, 1, C, D)) :|: TRUE
4.01/1.93	f0(A, B, C, D) -> Com_1(f12(B, 2, C, D)) :|: TRUE
4.01/1.93	f12(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE
4.01/1.93	f0(A, B, C, D) -> Com_1(f10001(B, B, C, 1)) :|: TRUE
4.01/1.93	f0(A, B, C, D) -> Com_1(f10001(B, 1, C, 1)) :|: TRUE
4.01/1.93	f100(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE
4.01/1.93	f110(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE
4.01/1.93	f120(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE
4.01/1.93	f1000(A, B, C, D) -> Com_1(f1200(A, 2, C, D)) :|: TRUE
4.01/1.93	f1000(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE
4.01/1.93	f1200(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE
4.01/1.93	f1000(A, B, C, D) -> Com_1(f10001(A, 1, C, 1)) :|: TRUE
4.01/1.93	
4.01/1.93	The start-symbols are:[f0_4]
4.01/1.93	
4.01/1.93	
4.01/1.93	----------------------------------------
4.01/1.93	
4.01/1.93	(1) Loat Proof (FINISHED)
4.01/1.93	
4.01/1.93	
4.01/1.93	### Pre-processing the ITS problem ###
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Initial linear ITS problem
4.01/1.93	
4.01/1.93	   Start location: f0
4.01/1.93	
4.01/1.93	      0: f0 -> f10001 : [], cost: 1
4.01/1.93	
4.01/1.93	     10: f0 -> f2 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     11: f0 -> f10001 : B'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     12: f0 -> f110 : A'=1, B'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     13: f0 -> f12 : A'=B, B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     15: f0 -> f10001 : A'=B, D'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     16: f0 -> f10001 : A'=B, B'=1, D'=1, [], cost: 1
4.01/1.93	
4.01/1.93	      1: f2 -> f2 : [], cost: 1
4.01/1.93	
4.01/1.93	      2: f2 -> f10001 : [], cost: 1
4.01/1.93	
4.01/1.93	      3: f2 -> f1200 : A'=B, [], cost: 1
4.01/1.93	
4.01/1.93	      4: f2200 -> f10000 : C'=0, [ C==0 ], cost: 1
4.01/1.93	
4.01/1.93	      5: f12 -> f12 : [], cost: 1
4.01/1.93	
4.01/1.93	     14: f12 -> f10001 : D'=1, [], cost: 1
4.01/1.93	
4.01/1.93	      6: f100 -> f110 : B'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     17: f100 -> f10001 : D'=1, [], cost: 1
4.01/1.93	
4.01/1.93	      7: f110 -> f120 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     18: f110 -> f10001 : D'=1, [], cost: 1
4.01/1.93	
4.01/1.93	      8: f120 -> f120 : [], cost: 1
4.01/1.93	
4.01/1.93	     19: f120 -> f10001 : D'=1, [], cost: 1
4.01/1.93	
4.01/1.93	      9: f1200 -> f1200 : [], cost: 1
4.01/1.93	
4.01/1.93	     22: f1200 -> f10001 : D'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     20: f1000 -> f1200 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     21: f1000 -> f10001 : D'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     23: f1000 -> f10001 : B'=1, D'=1, [], cost: 1
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Removed unreachable and leaf rules:
4.01/1.93	
4.01/1.93	   Start location: f0
4.01/1.93	
4.01/1.93	     10: f0 -> f2 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     12: f0 -> f110 : A'=1, B'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     13: f0 -> f12 : A'=B, B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	      1: f2 -> f2 : [], cost: 1
4.01/1.93	
4.01/1.93	      3: f2 -> f1200 : A'=B, [], cost: 1
4.01/1.93	
4.01/1.93	      5: f12 -> f12 : [], cost: 1
4.01/1.93	
4.01/1.93	      7: f110 -> f120 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	      8: f120 -> f120 : [], cost: 1
4.01/1.93	
4.01/1.93	      9: f1200 -> f1200 : [], cost: 1
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	### Simplification by acceleration and chaining ###
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Accelerating simple loops of location 1.
4.01/1.93	
4.01/1.93	   Accelerating the following rules:
4.01/1.93	
4.01/1.93	      1: f2 -> f2 : [], cost: 1
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	   Accelerated rule 1 with NONTERM, yielding the new rule 24.
4.01/1.93	
4.01/1.93	   Removing the simple loops: 1.
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Accelerating simple loops of location 3.
4.01/1.93	
4.01/1.93	   Accelerating the following rules:
4.01/1.93	
4.01/1.93	      5: f12 -> f12 : [], cost: 1
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	   Accelerated rule 5 with NONTERM, yielding the new rule 25.
4.01/1.93	
4.01/1.93	   Removing the simple loops: 5.
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Accelerating simple loops of location 6.
4.01/1.93	
4.01/1.93	   Accelerating the following rules:
4.01/1.93	
4.01/1.93	      8: f120 -> f120 : [], cost: 1
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	   Accelerated rule 8 with NONTERM, yielding the new rule 26.
4.01/1.93	
4.01/1.93	   Removing the simple loops: 8.
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Accelerating simple loops of location 7.
4.01/1.93	
4.01/1.93	   Accelerating the following rules:
4.01/1.93	
4.01/1.93	      9: f1200 -> f1200 : [], cost: 1
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	   Accelerated rule 9 with NONTERM, yielding the new rule 27.
4.01/1.93	
4.01/1.93	   Removing the simple loops: 9.
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Accelerated all simple loops using metering functions (where possible):
4.01/1.93	
4.01/1.93	   Start location: f0
4.01/1.93	
4.01/1.93	     10: f0 -> f2 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     12: f0 -> f110 : A'=1, B'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     13: f0 -> f12 : A'=B, B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	      3: f2 -> f1200 : A'=B, [], cost: 1
4.01/1.93	
4.01/1.93	     24: f2 -> [11] : [], cost: INF
4.01/1.93	
4.01/1.93	     25: f12 -> [12] : [], cost: INF
4.01/1.93	
4.01/1.93	      7: f110 -> f120 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     26: f120 -> [13] : [], cost: INF
4.01/1.93	
4.01/1.93	     27: f1200 -> [14] : [], cost: INF
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Chained accelerated rules (with incoming rules):
4.01/1.93	
4.01/1.93	   Start location: f0
4.01/1.93	
4.01/1.93	     10: f0 -> f2 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     12: f0 -> f110 : A'=1, B'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     13: f0 -> f12 : A'=B, B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     28: f0 -> [11] : B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	     29: f0 -> [12] : A'=B, B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	      3: f2 -> f1200 : A'=B, [], cost: 1
4.01/1.93	
4.01/1.93	     31: f2 -> [14] : A'=B, [], cost: INF
4.01/1.93	
4.01/1.93	      7: f110 -> f120 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     30: f110 -> [13] : B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Removed unreachable locations (and leaf rules with constant cost):
4.01/1.93	
4.01/1.93	   Start location: f0
4.01/1.93	
4.01/1.93	     10: f0 -> f2 : B'=2, [], cost: 1
4.01/1.93	
4.01/1.93	     12: f0 -> f110 : A'=1, B'=1, [], cost: 1
4.01/1.93	
4.01/1.93	     28: f0 -> [11] : B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	     29: f0 -> [12] : A'=B, B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	     31: f2 -> [14] : A'=B, [], cost: INF
4.01/1.93	
4.01/1.93	     30: f110 -> [13] : B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Eliminated locations (on linear paths):
4.01/1.93	
4.01/1.93	   Start location: f0
4.01/1.93	
4.01/1.93	     28: f0 -> [11] : B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	     29: f0 -> [12] : A'=B, B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	     32: f0 -> [14] : A'=2, B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	     33: f0 -> [13] : A'=1, B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	### Computing asymptotic complexity ###
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Fully simplified ITS problem
4.01/1.93	
4.01/1.93	   Start location: f0
4.01/1.93	
4.01/1.93	     33: f0 -> [13] : A'=1, B'=2, [], cost: INF
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Computing asymptotic complexity for rule 33
4.01/1.93	
4.01/1.93	   Resulting cost INF has complexity: Nonterm
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Found new complexity Nonterm.
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	Obtained the following overall complexity (w.r.t. the length of the input n):
4.01/1.93	
4.01/1.93	   Complexity:  Nonterm
4.01/1.93	
4.01/1.93	   Cpx degree:  Nonterm
4.01/1.93	
4.01/1.93	   Solved cost: INF
4.01/1.93	
4.01/1.93	   Rule cost:   INF
4.01/1.93	
4.01/1.93	   Rule guard:  []
4.01/1.93	
4.01/1.93	
4.01/1.93	
4.01/1.93	NO
4.01/1.93	
4.01/1.93	
4.01/1.93	----------------------------------------
4.01/1.93	
4.01/1.93	(2)
4.01/1.93	BOUNDS(INF, INF)
4.01/1.95	EOF