5.46/2.39	MAYBE
5.57/2.40	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
5.57/2.40	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.57/2.40	
5.57/2.40	
5.57/2.40	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, INF).
5.57/2.40	
5.57/2.40	(0) CpxIntTrs
5.57/2.40	(1) Loat Proof [FINISHED, 521 ms]
5.57/2.40	(2) BOUNDS(1, INF)
5.57/2.40	
5.57/2.40	
5.57/2.40	----------------------------------------
5.57/2.40	
5.57/2.40	(0)
5.57/2.40	Obligation:
5.57/2.40	Complexity Int TRS consisting of the following rules:
5.57/2.40	evalfstart(A, B) -> Com_1(evalfentryin(A, B)) :|: TRUE
5.57/2.40	evalfentryin(A, B) -> Com_1(evalfbb3in(B, A)) :|: A >= 1 && B >= A + 1
5.57/2.40	evalfbb3in(A, B) -> Com_1(evalfreturnin(A, B)) :|: 0 >= A
5.57/2.40	evalfbb3in(A, B) -> Com_1(evalfbb4in(A, B)) :|: A >= 1
5.57/2.40	evalfbb4in(A, B) -> Com_1(evalfbbin(A, B)) :|: 0 >= C + 1
5.57/2.40	evalfbb4in(A, B) -> Com_1(evalfbbin(A, B)) :|: C >= 1
5.57/2.40	evalfbb4in(A, B) -> Com_1(evalfreturnin(A, B)) :|: TRUE
5.57/2.40	evalfbbin(A, B) -> Com_1(evalfbb1in(A, B)) :|: B >= A + 1
5.57/2.40	evalfbbin(A, B) -> Com_1(evalfbb2in(A, B)) :|: A >= B
5.57/2.40	evalfbb1in(A, B) -> Com_1(evalfbb3in(A + 1, B)) :|: TRUE
5.57/2.40	evalfbb2in(A, B) -> Com_1(evalfbb3in(A - B, B)) :|: TRUE
5.57/2.40	evalfreturnin(A, B) -> Com_1(evalfstop(A, B)) :|: TRUE
5.57/2.40	
5.57/2.40	The start-symbols are:[evalfstart_2]
5.57/2.40	
5.57/2.40	
5.57/2.40	----------------------------------------
5.57/2.40	
5.57/2.40	(1) Loat Proof (FINISHED)
5.57/2.40	
5.57/2.40	
5.57/2.40	### Pre-processing the ITS problem ###
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Initial linear ITS problem
5.57/2.40	
5.57/2.40	   Start location: evalfstart
5.57/2.40	
5.57/2.40	      0: evalfstart -> evalfentryin : [], cost: 1
5.57/2.40	
5.57/2.40	      1: evalfentryin -> evalfbb3in : A'=B, B'=A, [ A>=1 && B>=1+A ], cost: 1
5.57/2.40	
5.57/2.40	      2: evalfbb3in -> evalfreturnin : [ 0>=A ], cost: 1
5.57/2.40	
5.57/2.40	      3: evalfbb3in -> evalfbb4in : [ A>=1 ], cost: 1
5.57/2.40	
5.57/2.40	      4: evalfbb4in -> evalfbbin : [ 0>=1+free ], cost: 1
5.57/2.40	
5.57/2.40	      5: evalfbb4in -> evalfbbin : [ free_1>=1 ], cost: 1
5.57/2.40	
5.57/2.40	      6: evalfbb4in -> evalfreturnin : [], cost: 1
5.57/2.40	
5.57/2.40	      7: evalfbbin -> evalfbb1in : [ B>=1+A ], cost: 1
5.57/2.40	
5.57/2.40	      8: evalfbbin -> evalfbb2in : [ A>=B ], cost: 1
5.57/2.40	
5.57/2.40	      9: evalfbb1in -> evalfbb3in : A'=1+A, [], cost: 1
5.57/2.40	
5.57/2.40	     10: evalfbb2in -> evalfbb3in : A'=A-B, [], cost: 1
5.57/2.40	
5.57/2.40	     11: evalfreturnin -> evalfstop : [], cost: 1
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Removed unreachable and leaf rules:
5.57/2.40	
5.57/2.40	   Start location: evalfstart
5.57/2.40	
5.57/2.40	      0: evalfstart -> evalfentryin : [], cost: 1
5.57/2.40	
5.57/2.40	      1: evalfentryin -> evalfbb3in : A'=B, B'=A, [ A>=1 && B>=1+A ], cost: 1
5.57/2.40	
5.57/2.40	      3: evalfbb3in -> evalfbb4in : [ A>=1 ], cost: 1
5.57/2.40	
5.57/2.40	      4: evalfbb4in -> evalfbbin : [ 0>=1+free ], cost: 1
5.57/2.40	
5.57/2.40	      5: evalfbb4in -> evalfbbin : [ free_1>=1 ], cost: 1
5.57/2.40	
5.57/2.40	      7: evalfbbin -> evalfbb1in : [ B>=1+A ], cost: 1
5.57/2.40	
5.57/2.40	      8: evalfbbin -> evalfbb2in : [ A>=B ], cost: 1
5.57/2.40	
5.57/2.40	      9: evalfbb1in -> evalfbb3in : A'=1+A, [], cost: 1
5.57/2.40	
5.57/2.40	     10: evalfbb2in -> evalfbb3in : A'=A-B, [], cost: 1
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Simplified all rules, resulting in:
5.57/2.40	
5.57/2.40	   Start location: evalfstart
5.57/2.40	
5.57/2.40	      0: evalfstart -> evalfentryin : [], cost: 1
5.57/2.40	
5.57/2.40	      1: evalfentryin -> evalfbb3in : A'=B, B'=A, [ A>=1 && B>=1+A ], cost: 1
5.57/2.40	
5.57/2.40	      3: evalfbb3in -> evalfbb4in : [ A>=1 ], cost: 1
5.57/2.40	
5.57/2.40	      5: evalfbb4in -> evalfbbin : [], cost: 1
5.57/2.40	
5.57/2.40	      7: evalfbbin -> evalfbb1in : [ B>=1+A ], cost: 1
5.57/2.40	
5.57/2.40	      8: evalfbbin -> evalfbb2in : [ A>=B ], cost: 1
5.57/2.40	
5.57/2.40	      9: evalfbb1in -> evalfbb3in : A'=1+A, [], cost: 1
5.57/2.40	
5.57/2.40	     10: evalfbb2in -> evalfbb3in : A'=A-B, [], cost: 1
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	### Simplification by acceleration and chaining ###
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Eliminated locations (on linear paths):
5.57/2.40	
5.57/2.40	   Start location: evalfstart
5.57/2.40	
5.57/2.40	     12: evalfstart -> evalfbb3in : A'=B, B'=A, [ A>=1 && B>=1+A ], cost: 2
5.57/2.40	
5.57/2.40	     13: evalfbb3in -> evalfbbin : [ A>=1 ], cost: 2
5.57/2.40	
5.57/2.40	     14: evalfbbin -> evalfbb3in : A'=1+A, [ B>=1+A ], cost: 2
5.57/2.40	
5.57/2.40	     15: evalfbbin -> evalfbb3in : A'=A-B, [ A>=B ], cost: 2
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Eliminated locations (on tree-shaped paths):
5.57/2.40	
5.57/2.40	   Start location: evalfstart
5.57/2.40	
5.57/2.40	     12: evalfstart -> evalfbb3in : A'=B, B'=A, [ A>=1 && B>=1+A ], cost: 2
5.57/2.40	
5.57/2.40	     16: evalfbb3in -> evalfbb3in : A'=1+A, [ A>=1 && B>=1+A ], cost: 4
5.57/2.40	
5.57/2.40	     17: evalfbb3in -> evalfbb3in : A'=A-B, [ A>=1 && A>=B ], cost: 4
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Accelerating simple loops of location 2.
5.57/2.40	
5.57/2.40	   Accelerating the following rules:
5.57/2.40	
5.57/2.40	     16: evalfbb3in -> evalfbb3in : A'=1+A, [ A>=1 && B>=1+A ], cost: 4
5.57/2.40	
5.57/2.40	     17: evalfbb3in -> evalfbb3in : A'=A-B, [ A>=1 && A>=B ], cost: 4
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	   Accelerated rule 16 with metering function -A+B, yielding the new rule 18.
5.57/2.40	
5.57/2.40	   Found no metering function for rule 17.
5.57/2.40	
5.57/2.40	   Removing the simple loops: 16.
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Accelerated all simple loops using metering functions (where possible):
5.57/2.40	
5.57/2.40	   Start location: evalfstart
5.57/2.40	
5.57/2.40	     12: evalfstart -> evalfbb3in : A'=B, B'=A, [ A>=1 && B>=1+A ], cost: 2
5.57/2.40	
5.57/2.40	     17: evalfbb3in -> evalfbb3in : A'=A-B, [ A>=1 && A>=B ], cost: 4
5.57/2.40	
5.57/2.40	     18: evalfbb3in -> evalfbb3in : A'=B, [ A>=1 && B>=1+A ], cost: -4*A+4*B
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Chained accelerated rules (with incoming rules):
5.57/2.40	
5.57/2.40	   Start location: evalfstart
5.57/2.40	
5.57/2.40	     12: evalfstart -> evalfbb3in : A'=B, B'=A, [ A>=1 && B>=1+A ], cost: 2
5.57/2.40	
5.57/2.40	     19: evalfstart -> evalfbb3in : A'=-A+B, B'=A, [ A>=1 && B>=1+A && B>=1 ], cost: 6
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Removed unreachable locations (and leaf rules with constant cost):
5.57/2.40	
5.57/2.40	   Start location: evalfstart
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	### Computing asymptotic complexity ###
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Fully simplified ITS problem
5.57/2.40	
5.57/2.40	   Start location: evalfstart
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	Obtained the following overall complexity (w.r.t. the length of the input n):
5.57/2.40	
5.57/2.40	   Complexity:  Unknown
5.57/2.40	
5.57/2.40	   Cpx degree:  ?
5.57/2.40	
5.57/2.40	   Solved cost: 0
5.57/2.40	
5.57/2.40	   Rule cost:   0
5.57/2.40	
5.57/2.40	   Rule guard:  []
5.57/2.40	
5.57/2.40	
5.57/2.40	
5.57/2.40	WORST_CASE(Omega(0),?)
5.57/2.40	
5.57/2.40	
5.57/2.40	----------------------------------------
5.57/2.40	
5.57/2.40	(2)
5.57/2.40	BOUNDS(1, INF)
5.57/2.43	EOF