4.99/2.23	MAYBE
4.99/2.24	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
4.99/2.24	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.99/2.24	
4.99/2.24	
4.99/2.24	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, INF).
4.99/2.24	
4.99/2.24	(0) CpxIntTrs
4.99/2.24	(1) Loat Proof [FINISHED, 515 ms]
4.99/2.24	(2) BOUNDS(1, INF)
4.99/2.24	
4.99/2.24	
4.99/2.24	----------------------------------------
4.99/2.24	
4.99/2.24	(0)
4.99/2.24	Obligation:
4.99/2.24	Complexity Int TRS consisting of the following rules:
4.99/2.24	evalgcdstart(A, B) -> Com_1(evalgcdentryin(A, B)) :|: TRUE
4.99/2.24	evalgcdentryin(A, B) -> Com_1(evalgcdreturnin(A, B)) :|: 0 >= A
4.99/2.24	evalgcdentryin(A, B) -> Com_1(evalgcdreturnin(A, B)) :|: 0 >= B
4.99/2.24	evalgcdentryin(A, B) -> Com_1(evalgcdbb7in(B, A)) :|: A >= 1 && B >= 1
4.99/2.24	evalgcdbb7in(A, B) -> Com_1(evalgcdbb4in(A, B)) :|: A >= B + 1
4.99/2.24	evalgcdbb7in(A, B) -> Com_1(evalgcdbb4in(A, B)) :|: B >= A + 1
4.99/2.24	evalgcdbb7in(A, B) -> Com_1(evalgcdreturnin(A, B)) :|: B >= A && B <= A
4.99/2.24	evalgcdbb4in(A, B) -> Com_1(evalgcdbb5in(A, B)) :|: A >= B + 1
4.99/2.24	evalgcdbb4in(A, B) -> Com_1(evalgcdbb6in(A, B)) :|: B >= A
4.99/2.24	evalgcdbb5in(A, B) -> Com_1(evalgcdbb7in(A - B, B)) :|: TRUE
4.99/2.24	evalgcdbb6in(A, B) -> Com_1(evalgcdbb7in(A, B - A)) :|: TRUE
4.99/2.24	evalgcdreturnin(A, B) -> Com_1(evalgcdstop(A, B)) :|: TRUE
4.99/2.24	
4.99/2.24	The start-symbols are:[evalgcdstart_2]
4.99/2.24	
4.99/2.24	
4.99/2.24	----------------------------------------
4.99/2.24	
4.99/2.24	(1) Loat Proof (FINISHED)
4.99/2.24	
4.99/2.24	
4.99/2.24	### Pre-processing the ITS problem ###
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Initial linear ITS problem
4.99/2.24	
4.99/2.24	   Start location: evalgcdstart
4.99/2.24	
4.99/2.24	      0: evalgcdstart -> evalgcdentryin : [], cost: 1
4.99/2.24	
4.99/2.24	      1: evalgcdentryin -> evalgcdreturnin : [ 0>=A ], cost: 1
4.99/2.24	
4.99/2.24	      2: evalgcdentryin -> evalgcdreturnin : [ 0>=B ], cost: 1
4.99/2.24	
4.99/2.24	      3: evalgcdentryin -> evalgcdbb7in : A'=B, B'=A, [ A>=1 && B>=1 ], cost: 1
4.99/2.24	
4.99/2.24	      4: evalgcdbb7in -> evalgcdbb4in : [ A>=1+B ], cost: 1
4.99/2.24	
4.99/2.24	      5: evalgcdbb7in -> evalgcdbb4in : [ B>=1+A ], cost: 1
4.99/2.24	
4.99/2.24	      6: evalgcdbb7in -> evalgcdreturnin : [ B==A ], cost: 1
4.99/2.24	
4.99/2.24	      7: evalgcdbb4in -> evalgcdbb5in : [ A>=1+B ], cost: 1
4.99/2.24	
4.99/2.24	      8: evalgcdbb4in -> evalgcdbb6in : [ B>=A ], cost: 1
4.99/2.24	
4.99/2.24	      9: evalgcdbb5in -> evalgcdbb7in : A'=A-B, [], cost: 1
4.99/2.24	
4.99/2.24	     10: evalgcdbb6in -> evalgcdbb7in : B'=-A+B, [], cost: 1
4.99/2.24	
4.99/2.24	     11: evalgcdreturnin -> evalgcdstop : [], cost: 1
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Removed unreachable and leaf rules:
4.99/2.24	
4.99/2.24	   Start location: evalgcdstart
4.99/2.24	
4.99/2.24	      0: evalgcdstart -> evalgcdentryin : [], cost: 1
4.99/2.24	
4.99/2.24	      3: evalgcdentryin -> evalgcdbb7in : A'=B, B'=A, [ A>=1 && B>=1 ], cost: 1
4.99/2.24	
4.99/2.24	      4: evalgcdbb7in -> evalgcdbb4in : [ A>=1+B ], cost: 1
4.99/2.24	
4.99/2.24	      5: evalgcdbb7in -> evalgcdbb4in : [ B>=1+A ], cost: 1
4.99/2.24	
4.99/2.24	      7: evalgcdbb4in -> evalgcdbb5in : [ A>=1+B ], cost: 1
4.99/2.24	
4.99/2.24	      8: evalgcdbb4in -> evalgcdbb6in : [ B>=A ], cost: 1
4.99/2.24	
4.99/2.24	      9: evalgcdbb5in -> evalgcdbb7in : A'=A-B, [], cost: 1
4.99/2.24	
4.99/2.24	     10: evalgcdbb6in -> evalgcdbb7in : B'=-A+B, [], cost: 1
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	### Simplification by acceleration and chaining ###
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Eliminated locations (on linear paths):
4.99/2.24	
4.99/2.24	   Start location: evalgcdstart
4.99/2.24	
4.99/2.24	     12: evalgcdstart -> evalgcdbb7in : A'=B, B'=A, [ A>=1 && B>=1 ], cost: 2
4.99/2.24	
4.99/2.24	      4: evalgcdbb7in -> evalgcdbb4in : [ A>=1+B ], cost: 1
4.99/2.24	
4.99/2.24	      5: evalgcdbb7in -> evalgcdbb4in : [ B>=1+A ], cost: 1
4.99/2.24	
4.99/2.24	     13: evalgcdbb4in -> evalgcdbb7in : A'=A-B, [ A>=1+B ], cost: 2
4.99/2.24	
4.99/2.24	     14: evalgcdbb4in -> evalgcdbb7in : B'=-A+B, [ B>=A ], cost: 2
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Eliminated locations (on tree-shaped paths):
4.99/2.24	
4.99/2.24	   Start location: evalgcdstart
4.99/2.24	
4.99/2.24	     12: evalgcdstart -> evalgcdbb7in : A'=B, B'=A, [ A>=1 && B>=1 ], cost: 2
4.99/2.24	
4.99/2.24	     15: evalgcdbb7in -> evalgcdbb7in : A'=A-B, [ A>=1+B ], cost: 3
4.99/2.24	
4.99/2.24	     16: evalgcdbb7in -> evalgcdbb7in : B'=-A+B, [ B>=1+A ], cost: 3
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Accelerating simple loops of location 2.
4.99/2.24	
4.99/2.24	   Accelerating the following rules:
4.99/2.24	
4.99/2.24	     15: evalgcdbb7in -> evalgcdbb7in : A'=A-B, [ A>=1+B ], cost: 3
4.99/2.24	
4.99/2.24	     16: evalgcdbb7in -> evalgcdbb7in : B'=-A+B, [ B>=1+A ], cost: 3
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	   Found no metering function for rule 15.
4.99/2.24	
4.99/2.24	   Found no metering function for rule 16.
4.99/2.24	
4.99/2.24	   Removing the simple loops:.
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Accelerated all simple loops using metering functions (where possible):
4.99/2.24	
4.99/2.24	   Start location: evalgcdstart
4.99/2.24	
4.99/2.24	     12: evalgcdstart -> evalgcdbb7in : A'=B, B'=A, [ A>=1 && B>=1 ], cost: 2
4.99/2.24	
4.99/2.24	     15: evalgcdbb7in -> evalgcdbb7in : A'=A-B, [ A>=1+B ], cost: 3
4.99/2.24	
4.99/2.24	     16: evalgcdbb7in -> evalgcdbb7in : B'=-A+B, [ B>=1+A ], cost: 3
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Chained accelerated rules (with incoming rules):
4.99/2.24	
4.99/2.24	   Start location: evalgcdstart
4.99/2.24	
4.99/2.24	     12: evalgcdstart -> evalgcdbb7in : A'=B, B'=A, [ A>=1 && B>=1 ], cost: 2
4.99/2.24	
4.99/2.24	     17: evalgcdstart -> evalgcdbb7in : A'=-A+B, B'=A, [ A>=1 && B>=1 && B>=1+A ], cost: 5
4.99/2.24	
4.99/2.24	     18: evalgcdstart -> evalgcdbb7in : A'=B, B'=A-B, [ A>=1 && B>=1 && A>=1+B ], cost: 5
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Removed unreachable locations (and leaf rules with constant cost):
4.99/2.24	
4.99/2.24	   Start location: evalgcdstart
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	### Computing asymptotic complexity ###
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Fully simplified ITS problem
4.99/2.24	
4.99/2.24	   Start location: evalgcdstart
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	Obtained the following overall complexity (w.r.t. the length of the input n):
4.99/2.24	
4.99/2.24	   Complexity:  Unknown
4.99/2.24	
4.99/2.24	   Cpx degree:  ?
4.99/2.24	
4.99/2.24	   Solved cost: 0
4.99/2.24	
4.99/2.24	   Rule cost:   0
4.99/2.24	
4.99/2.24	   Rule guard:  []
4.99/2.24	
4.99/2.24	
4.99/2.24	
4.99/2.24	WORST_CASE(Omega(0),?)
4.99/2.24	
4.99/2.24	
4.99/2.24	----------------------------------------
4.99/2.24	
4.99/2.24	(2)
4.99/2.24	BOUNDS(1, INF)
4.99/2.27	EOF