3.49/2.15	WORST_CASE(NON_POLY, ?)
4.23/2.16	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.23/2.16	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.23/2.16	
4.23/2.16	
4.23/2.16	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
4.23/2.16	
4.23/2.16	(0) CpxIntTrs
4.23/2.16	(1) Loat Proof [FINISHED, 255 ms]
4.23/2.16	(2) BOUNDS(INF, INF)
4.23/2.16	
4.23/2.16	
4.23/2.16	----------------------------------------
4.23/2.16	
4.23/2.16	(0)
4.23/2.16	Obligation:
4.23/2.16	Complexity Int TRS consisting of the following rules:
4.23/2.16	f0(A, B, C, D, E, F, G) -> Com_1(f12(H, I, J, 0, E, F, G)) :|: TRUE
4.23/2.16	f12(A, B, C, D, E, F, G) -> Com_1(f12(A, B, C, D + 1, E, F, G)) :|: C >= D + 1
4.23/2.16	f25(A, B, C, D, E, F, G) -> Com_1(f25(A, B, C, D, E, F + 1, G)) :|: E >= F + 1
4.23/2.16	f25(A, B, C, D, E, F, G) -> Com_1(f34(A, B, C, D, E, F, G)) :|: F >= E
4.23/2.16	f12(A, B, C, D, E, F, G) -> Com_1(f25(A, B, C, D, A, 0, H)) :|: D >= C
4.23/2.16	
4.23/2.16	The start-symbols are:[f0_7]
4.23/2.16	
4.23/2.16	
4.23/2.16	----------------------------------------
4.23/2.16	
4.23/2.16	(1) Loat Proof (FINISHED)
4.23/2.16	
4.23/2.16	
4.23/2.16	### Pre-processing the ITS problem ###
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Initial linear ITS problem
4.23/2.16	
4.23/2.16	   Start location: f0
4.23/2.16	
4.23/2.16	      0: f0 -> f12 : A'=free_2, B'=free, C'=free_1, D'=0, [], cost: 1
4.23/2.16	
4.23/2.16	      1: f12 -> f12 : D'=1+D, [ C>=1+D ], cost: 1
4.23/2.16	
4.23/2.16	      4: f12 -> f25 : E'=A, F'=0, G'=free_3, [ D>=C ], cost: 1
4.23/2.16	
4.23/2.16	      2: f25 -> f25 : F'=1+F, [ E>=1+F ], cost: 1
4.23/2.16	
4.23/2.16	      3: f25 -> f34 : [ F>=E ], cost: 1
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Removed unreachable and leaf rules:
4.23/2.16	
4.23/2.16	   Start location: f0
4.23/2.16	
4.23/2.16	      0: f0 -> f12 : A'=free_2, B'=free, C'=free_1, D'=0, [], cost: 1
4.23/2.16	
4.23/2.16	      1: f12 -> f12 : D'=1+D, [ C>=1+D ], cost: 1
4.23/2.16	
4.23/2.16	      4: f12 -> f25 : E'=A, F'=0, G'=free_3, [ D>=C ], cost: 1
4.23/2.16	
4.23/2.16	      2: f25 -> f25 : F'=1+F, [ E>=1+F ], cost: 1
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	### Simplification by acceleration and chaining ###
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Accelerating simple loops of location 1.
4.23/2.16	
4.23/2.16	   Accelerating the following rules:
4.23/2.16	
4.23/2.16	      1: f12 -> f12 : D'=1+D, [ C>=1+D ], cost: 1
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	   Accelerated rule 1 with metering function C-D, yielding the new rule 5.
4.23/2.16	
4.23/2.16	   Removing the simple loops: 1.
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Accelerating simple loops of location 2.
4.23/2.16	
4.23/2.16	   Accelerating the following rules:
4.23/2.16	
4.23/2.16	      2: f25 -> f25 : F'=1+F, [ E>=1+F ], cost: 1
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	   Accelerated rule 2 with metering function -F+E, yielding the new rule 6.
4.23/2.16	
4.23/2.16	   Removing the simple loops: 2.
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Accelerated all simple loops using metering functions (where possible):
4.23/2.16	
4.23/2.16	   Start location: f0
4.23/2.16	
4.23/2.16	      0: f0 -> f12 : A'=free_2, B'=free, C'=free_1, D'=0, [], cost: 1
4.23/2.16	
4.23/2.16	      4: f12 -> f25 : E'=A, F'=0, G'=free_3, [ D>=C ], cost: 1
4.23/2.16	
4.23/2.16	      5: f12 -> f12 : D'=C, [ C>=1+D ], cost: C-D
4.23/2.16	
4.23/2.16	      6: f25 -> f25 : F'=E, [ E>=1+F ], cost: -F+E
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Chained accelerated rules (with incoming rules):
4.23/2.16	
4.23/2.16	   Start location: f0
4.23/2.16	
4.23/2.16	      0: f0 -> f12 : A'=free_2, B'=free, C'=free_1, D'=0, [], cost: 1
4.23/2.16	
4.23/2.16	      7: f0 -> f12 : A'=free_2, B'=free, C'=free_1, D'=free_1, [ free_1>=1 ], cost: 1+free_1
4.23/2.16	
4.23/2.16	      4: f12 -> f25 : E'=A, F'=0, G'=free_3, [ D>=C ], cost: 1
4.23/2.16	
4.23/2.16	      8: f12 -> f25 : E'=A, F'=A, G'=free_3, [ D>=C && A>=1 ], cost: 1+A
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Removed unreachable locations (and leaf rules with constant cost):
4.23/2.16	
4.23/2.16	   Start location: f0
4.23/2.16	
4.23/2.16	      0: f0 -> f12 : A'=free_2, B'=free, C'=free_1, D'=0, [], cost: 1
4.23/2.16	
4.23/2.16	      7: f0 -> f12 : A'=free_2, B'=free, C'=free_1, D'=free_1, [ free_1>=1 ], cost: 1+free_1
4.23/2.16	
4.23/2.16	      8: f12 -> f25 : E'=A, F'=A, G'=free_3, [ D>=C && A>=1 ], cost: 1+A
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Eliminated locations (on tree-shaped paths):
4.23/2.16	
4.23/2.16	   Start location: f0
4.23/2.16	
4.23/2.16	      9: f0 -> f25 : A'=free_2, B'=free, C'=free_1, D'=0, E'=free_2, F'=free_2, G'=free_3, [ 0>=free_1 && free_2>=1 ], cost: 2+free_2
4.23/2.16	
4.23/2.16	     10: f0 -> f25 : A'=free_2, B'=free, C'=free_1, D'=free_1, E'=free_2, F'=free_2, G'=free_3, [ free_1>=1 && free_2>=1 ], cost: 2+free_1+free_2
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	### Computing asymptotic complexity ###
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Fully simplified ITS problem
4.23/2.16	
4.23/2.16	   Start location: f0
4.23/2.16	
4.23/2.16	      9: f0 -> f25 : A'=free_2, B'=free, C'=free_1, D'=0, E'=free_2, F'=free_2, G'=free_3, [ 0>=free_1 && free_2>=1 ], cost: 2+free_2
4.23/2.16	
4.23/2.16	     10: f0 -> f25 : A'=free_2, B'=free, C'=free_1, D'=free_1, E'=free_2, F'=free_2, G'=free_3, [ free_1>=1 && free_2>=1 ], cost: 2+free_1+free_2
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Computing asymptotic complexity for rule 9
4.23/2.16	
4.23/2.16	   Solved the limit problem by the following transformations:
4.23/2.16	
4.23/2.16	      Created initial limit problem:
4.23/2.16	
4.23/2.16	      2+free_2 (+), 1-free_1 (+/+!), free_2 (+/+!) [not solved]
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	      removing all constraints (solved by SMT)
4.23/2.16	
4.23/2.16	      resulting limit problem: [solved]
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	      applying transformation rule (C) using substitution {free_1==-n,free_2==n}
4.23/2.16	
4.23/2.16	      resulting limit problem:
4.23/2.16	
4.23/2.16	      [solved]
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	   Solution:
4.23/2.16	
4.23/2.16	      free_1 / -n
4.23/2.16	
4.23/2.16	      free_2 / n
4.23/2.16	
4.23/2.16	   Resulting cost 2+n has complexity: Unbounded
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Found new complexity Unbounded.
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	Obtained the following overall complexity (w.r.t. the length of the input n):
4.23/2.16	
4.23/2.16	   Complexity:  Unbounded
4.23/2.16	
4.23/2.16	   Cpx degree:  Unbounded
4.23/2.16	
4.23/2.16	   Solved cost: 2+n
4.23/2.16	
4.23/2.16	   Rule cost:   2+free_2
4.23/2.16	
4.23/2.16	   Rule guard:  [ 0>=free_1 && free_2>=1 ]
4.23/2.16	
4.23/2.16	
4.23/2.16	
4.23/2.16	WORST_CASE(INF,?)
4.23/2.16	
4.23/2.16	
4.23/2.16	----------------------------------------
4.23/2.16	
4.23/2.16	(2)
4.23/2.16	BOUNDS(INF, INF)
4.23/2.17	EOF