4.78/2.09	WORST_CASE(NON_POLY, ?)
4.78/2.10	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.78/2.10	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.78/2.10	
4.78/2.10	
4.78/2.10	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
4.78/2.10	
4.78/2.10	(0) CpxIntTrs
4.78/2.10	(1) Loat Proof [FINISHED, 405 ms]
4.78/2.10	(2) BOUNDS(INF, INF)
4.78/2.10	
4.78/2.10	
4.78/2.10	----------------------------------------
4.78/2.10	
4.78/2.10	(0)
4.78/2.10	Obligation:
4.78/2.10	Complexity Int TRS consisting of the following rules:
4.78/2.10	f0(A, B, C, D, E) -> Com_1(f9(F, F, F, 0, E)) :|: TRUE
4.78/2.10	f9(A, B, C, D, E) -> Com_1(f9(A, B, C, D + 1, F)) :|: C >= D + 1
4.78/2.10	f24(A, B, C, D, E) -> Com_1(f24(A, B, C, D, E)) :|: 0 >= F + 1
4.78/2.10	f24(A, B, C, D, E) -> Com_1(f24(A, B, C, D, E)) :|: TRUE
4.78/2.10	f37(A, B, C, D, E) -> Com_1(f37(A, B, C, D, E)) :|: F >= G + 1
4.78/2.10	f37(A, B, C, D, E) -> Com_1(f37(A, B, C, D, E)) :|: TRUE
4.78/2.10	f37(A, B, C, D, E) -> Com_1(f48(A, B, C, D, E)) :|: TRUE
4.78/2.10	f24(A, B, C, D, E) -> Com_1(f37(A, B, C, D, E)) :|: TRUE
4.78/2.10	f9(A, B, C, D, E) -> Com_1(f24(A, B, C, D, E)) :|: D >= C
4.78/2.10	
4.78/2.10	The start-symbols are:[f0_5]
4.78/2.10	
4.78/2.10	
4.78/2.10	----------------------------------------
4.78/2.10	
4.78/2.10	(1) Loat Proof (FINISHED)
4.78/2.10	
4.78/2.10	
4.78/2.10	### Pre-processing the ITS problem ###
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Initial linear ITS problem
4.78/2.10	
4.78/2.10	   Start location: f0
4.78/2.10	
4.78/2.10	      0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1
4.78/2.10	
4.78/2.10	      1: f9 -> f9 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1
4.78/2.10	
4.78/2.10	      8: f9 -> f24 : [ D>=C ], cost: 1
4.78/2.10	
4.78/2.10	      2: f24 -> f24 : [ 0>=1+free_2 ], cost: 1
4.78/2.10	
4.78/2.10	      3: f24 -> f24 : [], cost: 1
4.78/2.10	
4.78/2.10	      7: f24 -> f37 : [], cost: 1
4.78/2.10	
4.78/2.10	      4: f37 -> f37 : [ free_3>=1+free_4 ], cost: 1
4.78/2.10	
4.78/2.10	      5: f37 -> f37 : [], cost: 1
4.78/2.10	
4.78/2.10	      6: f37 -> f48 : [], cost: 1
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Removed unreachable and leaf rules:
4.78/2.10	
4.78/2.10	   Start location: f0
4.78/2.10	
4.78/2.10	      0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1
4.78/2.10	
4.78/2.10	      1: f9 -> f9 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1
4.78/2.10	
4.78/2.10	      8: f9 -> f24 : [ D>=C ], cost: 1
4.78/2.10	
4.78/2.10	      2: f24 -> f24 : [ 0>=1+free_2 ], cost: 1
4.78/2.10	
4.78/2.10	      3: f24 -> f24 : [], cost: 1
4.78/2.10	
4.78/2.10	      7: f24 -> f37 : [], cost: 1
4.78/2.10	
4.78/2.10	      4: f37 -> f37 : [ free_3>=1+free_4 ], cost: 1
4.78/2.10	
4.78/2.10	      5: f37 -> f37 : [], cost: 1
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Simplified all rules, resulting in:
4.78/2.10	
4.78/2.10	   Start location: f0
4.78/2.10	
4.78/2.10	      0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1
4.78/2.10	
4.78/2.10	      1: f9 -> f9 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1
4.78/2.10	
4.78/2.10	      8: f9 -> f24 : [ D>=C ], cost: 1
4.78/2.10	
4.78/2.10	      3: f24 -> f24 : [], cost: 1
4.78/2.10	
4.78/2.10	      7: f24 -> f37 : [], cost: 1
4.78/2.10	
4.78/2.10	      5: f37 -> f37 : [], cost: 1
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	### Simplification by acceleration and chaining ###
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Accelerating simple loops of location 1.
4.78/2.10	
4.78/2.10	   Accelerating the following rules:
4.78/2.10	
4.78/2.10	      1: f9 -> f9 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	   Accelerated rule 1 with metering function C-D, yielding the new rule 9.
4.78/2.10	
4.78/2.10	   Removing the simple loops: 1.
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Accelerating simple loops of location 2.
4.78/2.10	
4.78/2.10	   Accelerating the following rules:
4.78/2.10	
4.78/2.10	      3: f24 -> f24 : [], cost: 1
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	   Accelerated rule 3 with NONTERM, yielding the new rule 10.
4.78/2.10	
4.78/2.10	   Removing the simple loops: 3.
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Accelerating simple loops of location 3.
4.78/2.10	
4.78/2.10	   Accelerating the following rules:
4.78/2.10	
4.78/2.10	      5: f37 -> f37 : [], cost: 1
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	   Accelerated rule 5 with NONTERM, yielding the new rule 11.
4.78/2.10	
4.78/2.10	   Removing the simple loops: 5.
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Accelerated all simple loops using metering functions (where possible):
4.78/2.10	
4.78/2.10	   Start location: f0
4.78/2.10	
4.78/2.10	      0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1
4.78/2.10	
4.78/2.10	      8: f9 -> f24 : [ D>=C ], cost: 1
4.78/2.10	
4.78/2.10	      9: f9 -> f9 : D'=C, E'=free_1, [ C>=1+D ], cost: C-D
4.78/2.10	
4.78/2.10	      7: f24 -> f37 : [], cost: 1
4.78/2.10	
4.78/2.10	     10: f24 -> [6] : [], cost: INF
4.78/2.10	
4.78/2.10	     11: f37 -> [7] : [], cost: INF
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Chained accelerated rules (with incoming rules):
4.78/2.10	
4.78/2.10	   Start location: f0
4.78/2.10	
4.78/2.10	      0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1
4.78/2.10	
4.78/2.10	     12: f0 -> f9 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 1+free
4.78/2.10	
4.78/2.10	      8: f9 -> f24 : [ D>=C ], cost: 1
4.78/2.10	
4.78/2.10	     13: f9 -> [6] : [ D>=C ], cost: INF
4.78/2.10	
4.78/2.10	      7: f24 -> f37 : [], cost: 1
4.78/2.10	
4.78/2.10	     14: f24 -> [7] : [], cost: INF
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Removed unreachable locations (and leaf rules with constant cost):
4.78/2.10	
4.78/2.10	   Start location: f0
4.78/2.10	
4.78/2.10	      0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1
4.78/2.10	
4.78/2.10	     12: f0 -> f9 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 1+free
4.78/2.10	
4.78/2.10	      8: f9 -> f24 : [ D>=C ], cost: 1
4.78/2.10	
4.78/2.10	     13: f9 -> [6] : [ D>=C ], cost: INF
4.78/2.10	
4.78/2.10	     14: f24 -> [7] : [], cost: INF
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Eliminated locations (on linear paths):
4.78/2.10	
4.78/2.10	   Start location: f0
4.78/2.10	
4.78/2.10	      0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1
4.78/2.10	
4.78/2.10	     12: f0 -> f9 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 1+free
4.78/2.10	
4.78/2.10	     13: f9 -> [6] : [ D>=C ], cost: INF
4.78/2.10	
4.78/2.10	     15: f9 -> [7] : [ D>=C ], cost: INF
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Eliminated locations (on tree-shaped paths):
4.78/2.10	
4.78/2.10	   Start location: f0
4.78/2.10	
4.78/2.10	     16: f0 -> [6] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: INF
4.78/2.10	
4.78/2.10	     17: f0 -> [7] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: INF
4.78/2.10	
4.78/2.10	     18: f0 -> [6] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: INF
4.78/2.10	
4.78/2.10	     19: f0 -> [7] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: INF
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	### Computing asymptotic complexity ###
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Fully simplified ITS problem
4.78/2.10	
4.78/2.10	   Start location: f0
4.78/2.10	
4.78/2.10	     17: f0 -> [7] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: INF
4.78/2.10	
4.78/2.10	     19: f0 -> [7] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: INF
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Computing asymptotic complexity for rule 17
4.78/2.10	
4.78/2.10	   Resulting cost INF has complexity: Nonterm
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Found new complexity Nonterm.
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	Obtained the following overall complexity (w.r.t. the length of the input n):
4.78/2.10	
4.78/2.10	   Complexity:  Nonterm
4.78/2.10	
4.78/2.10	   Cpx degree:  Nonterm
4.78/2.10	
4.78/2.10	   Solved cost: INF
4.78/2.10	
4.78/2.10	   Rule cost:   INF
4.78/2.10	
4.78/2.10	   Rule guard:  [ 0>=free ]
4.78/2.10	
4.78/2.10	
4.78/2.10	
4.78/2.10	NO
4.78/2.10	
4.78/2.10	
4.78/2.10	----------------------------------------
4.78/2.10	
4.78/2.10	(2)
4.78/2.10	BOUNDS(INF, INF)
4.78/2.12	EOF