4.40/2.18	WORST_CASE(Omega(n^1), O(n^1))
4.40/2.18	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.40/2.18	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.40/2.18	
4.40/2.18	
4.40/2.18	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(2, 2 + Arg_1) + nat(Arg_0) + nat(Arg_1)).
4.40/2.18	
4.40/2.18	(0) CpxIntTrs
4.40/2.18	(1) Koat2 Proof [FINISHED, 422 ms]
4.40/2.18	(2) BOUNDS(1, max(2, 2 + Arg_1) + nat(Arg_0) + nat(Arg_1))
4.40/2.18	(3) Loat Proof [FINISHED, 434 ms]
4.40/2.18	(4) BOUNDS(n^1, INF)
4.40/2.18	
4.40/2.18	
4.40/2.18	----------------------------------------
4.40/2.18	
4.40/2.18	(0)
4.40/2.18	Obligation:
4.40/2.18	Complexity Int TRS consisting of the following rules:
4.40/2.18	f2(A, B, C) -> Com_1(f2(-(1) + A, B, C)) :|: A >= 31
4.40/2.18	f2(A, B, C) -> Com_1(f300(A, -(1) + B, C)) :|: 30 >= A
4.40/2.18	f300(A, B, C) -> Com_1(f2(A, B, C)) :|: B >= 21
4.40/2.18	f300(A, B, C) -> Com_1(f1(A, B, D)) :|: 20 >= B
4.40/2.18	f3(A, B, C) -> Com_1(f300(A, B, C)) :|: TRUE
4.40/2.18	
4.40/2.18	The start-symbols are:[f3_3]
4.40/2.18	
4.40/2.18	
4.40/2.18	----------------------------------------
4.40/2.18	
4.40/2.18	(1) Koat2 Proof (FINISHED)
4.40/2.18	YES( ?, 2+max([0, Arg_1])+max([0, Arg_0])+max([0, Arg_1]) {O(n)})
4.40/2.18	
4.40/2.18	
4.40/2.18	
4.40/2.18	Initial Complexity Problem:
4.40/2.18	
4.40/2.18	  Start:  f3  
4.40/2.18	
4.40/2.18	  Program_Vars:  Arg_0, Arg_1, Arg_2  
4.40/2.18	
4.40/2.18	  Temp_Vars:  D  
4.40/2.18	
4.40/2.18	  Locations:  f1, f2, f3, f300  
4.40/2.18	
4.40/2.18	  Transitions:
4.40/2.18	
4.40/2.18	  f2(Arg_0,Arg_1,Arg_2) -> f2(-1+Arg_0,Arg_1,Arg_2):|:21 <= Arg_1 && 31 <= Arg_0
4.40/2.18	
4.40/2.18	  f2(Arg_0,Arg_1,Arg_2) -> f300(Arg_0,-1+Arg_1,Arg_2):|:21 <= Arg_1 && Arg_0 <= 30
4.40/2.18	
4.40/2.18	  f3(Arg_0,Arg_1,Arg_2) -> f300(Arg_0,Arg_1,Arg_2):|:
4.40/2.18	
4.40/2.18	  f300(Arg_0,Arg_1,Arg_2) -> f1(Arg_0,Arg_1,D):|:Arg_1 <= 20
4.40/2.18	
4.40/2.18	  f300(Arg_0,Arg_1,Arg_2) -> f2(Arg_0,Arg_1,Arg_2):|:21 <= Arg_1  
4.40/2.18	
4.40/2.18	
4.40/2.18	
4.40/2.18	Timebounds: 
4.40/2.18	
4.40/2.18	  Overall timebound: 2+max([0, Arg_1])+max([0, Arg_0])+max([0, Arg_1]) {O(n)}
4.40/2.18	
4.40/2.18	  0: f2->f2: max([0, Arg_0]) {O(n)}
4.40/2.18	
4.40/2.18	  1: f2->f300: max([0, Arg_1]) {O(n)}
4.40/2.18	
4.40/2.18	  4: f3->f300: 1 {O(1)}
4.40/2.18	
4.40/2.18	  2: f300->f2: max([0, Arg_1]) {O(n)}
4.40/2.18	
4.40/2.18	  3: f300->f1: 1 {O(1)}
4.40/2.18	
4.40/2.18	
4.40/2.18	
4.40/2.18	Costbounds:
4.40/2.18	
4.40/2.18	  Overall costbound: 2+max([0, Arg_1])+max([0, Arg_0])+max([0, Arg_1]) {O(n)}
4.40/2.18	
4.40/2.18	  0: f2->f2: max([0, Arg_0]) {O(n)}
4.40/2.18	
4.40/2.18	  1: f2->f300: max([0, Arg_1]) {O(n)}
4.40/2.18	
4.40/2.18	  4: f3->f300: 1 {O(1)}
4.40/2.18	
4.40/2.18	  2: f300->f2: max([0, Arg_1]) {O(n)}
4.40/2.18	
4.40/2.18	  3: f300->f1: 1 {O(1)}
4.40/2.18	
4.40/2.18	
4.40/2.18	
4.40/2.18	Sizebounds:
4.40/2.18	
4.40/2.18	`Lower:
4.40/2.18	
4.40/2.18	  0: f2->f2, Arg_0: 30 {O(1)}
4.40/2.18	
4.40/2.18	  0: f2->f2, Arg_1: 21 {O(1)}
4.40/2.18	
4.40/2.18	  0: f2->f2, Arg_2: Arg_2 {O(n)}
4.40/2.18	
4.40/2.18	  1: f2->f300, Arg_0: min([30, Arg_0]) {O(n)}
4.40/2.18	
4.40/2.18	  1: f2->f300, Arg_1: 20 {O(1)}
4.40/2.18	
4.40/2.18	  1: f2->f300, Arg_2: Arg_2 {O(n)}
4.40/2.18	
4.40/2.18	  4: f3->f300, Arg_0: Arg_0 {O(n)}
4.40/2.18	
4.40/2.18	  4: f3->f300, Arg_1: Arg_1 {O(n)}
4.40/2.18	
4.40/2.18	  4: f3->f300, Arg_2: Arg_2 {O(n)}
4.40/2.18	
4.40/2.18	  2: f300->f2, Arg_0: min([30, Arg_0]) {O(n)}
4.40/2.18	
4.40/2.18	  2: f300->f2, Arg_1: 21 {O(1)}
4.40/2.18	
4.40/2.18	  2: f300->f2, Arg_2: Arg_2 {O(n)}
4.40/2.18	
4.40/2.18	  3: f300->f1, Arg_0: min([30, Arg_0]) {O(n)}
4.40/2.18	
4.40/2.18	  3: f300->f1, Arg_1: min([20, Arg_1]) {O(n)}
4.40/2.18	
4.40/2.18	`Upper:
4.40/2.18	
4.40/2.18	  0: f2->f2, Arg_0: max([30, Arg_0]) {O(n)}
4.40/2.18	
4.40/2.18	  0: f2->f2, Arg_1: Arg_1 {O(n)}
4.40/2.18	
4.40/2.18	  0: f2->f2, Arg_2: Arg_2 {O(n)}
4.40/2.18	
4.40/2.18	  1: f2->f300, Arg_0: 30 {O(1)}
4.40/2.18	
4.40/2.18	  1: f2->f300, Arg_1: Arg_1 {O(n)}
4.40/2.18	
4.40/2.18	  1: f2->f300, Arg_2: Arg_2 {O(n)}
4.40/2.18	
4.40/2.18	  4: f3->f300, Arg_0: Arg_0 {O(n)}
4.40/2.18	
4.40/2.18	  4: f3->f300, Arg_1: Arg_1 {O(n)}
4.40/2.18	
4.40/2.18	  4: f3->f300, Arg_2: Arg_2 {O(n)}
4.40/2.18	
4.40/2.18	  2: f300->f2, Arg_0: max([30, Arg_0]) {O(n)}
4.40/2.18	
4.40/2.18	  2: f300->f2, Arg_1: Arg_1 {O(n)}
4.40/2.18	
4.40/2.18	  2: f300->f2, Arg_2: Arg_2 {O(n)}
4.40/2.18	
4.40/2.18	  3: f300->f1, Arg_0: max([30, Arg_0]) {O(n)}
4.40/2.18	
4.40/2.18	  3: f300->f1, Arg_1: 20 {O(1)}
4.40/2.19	
4.40/2.19	
4.40/2.19	----------------------------------------
4.40/2.19	
4.40/2.19	(2)
4.40/2.19	BOUNDS(1, max(2, 2 + Arg_1) + nat(Arg_0) + nat(Arg_1))
4.40/2.19	
4.40/2.19	----------------------------------------
4.40/2.19	
4.40/2.19	(3) Loat Proof (FINISHED)
4.40/2.19	
4.40/2.19	
4.40/2.19	### Pre-processing the ITS problem ###
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Initial linear ITS problem
4.40/2.19	
4.40/2.19	   Start location: f3
4.40/2.19	
4.40/2.19	      0: f2 -> f2 : A'=-1+A, [ A>=31 ], cost: 1
4.40/2.19	
4.40/2.19	      1: f2 -> f300 : B'=-1+B, [ 30>=A ], cost: 1
4.40/2.19	
4.40/2.19	      2: f300 -> f2 : [ B>=21 ], cost: 1
4.40/2.19	
4.40/2.19	      3: f300 -> f1 : C'=free, [ 20>=B ], cost: 1
4.40/2.19	
4.40/2.19	      4: f3 -> f300 : [], cost: 1
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Removed unreachable and leaf rules:
4.40/2.19	
4.40/2.19	   Start location: f3
4.40/2.19	
4.40/2.19	      0: f2 -> f2 : A'=-1+A, [ A>=31 ], cost: 1
4.40/2.19	
4.40/2.19	      1: f2 -> f300 : B'=-1+B, [ 30>=A ], cost: 1
4.40/2.19	
4.40/2.19	      2: f300 -> f2 : [ B>=21 ], cost: 1
4.40/2.19	
4.40/2.19	      4: f3 -> f300 : [], cost: 1
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	### Simplification by acceleration and chaining ###
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Accelerating simple loops of location 0.
4.40/2.19	
4.40/2.19	   Accelerating the following rules:
4.40/2.19	
4.40/2.19	      0: f2 -> f2 : A'=-1+A, [ A>=31 ], cost: 1
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	   Accelerated rule 0 with metering function -30+A, yielding the new rule 5.
4.40/2.19	
4.40/2.19	   Removing the simple loops: 0.
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Accelerated all simple loops using metering functions (where possible):
4.40/2.19	
4.40/2.19	   Start location: f3
4.40/2.19	
4.40/2.19	      1: f2 -> f300 : B'=-1+B, [ 30>=A ], cost: 1
4.40/2.19	
4.40/2.19	      5: f2 -> f2 : A'=30, [ A>=31 ], cost: -30+A
4.40/2.19	
4.40/2.19	      2: f300 -> f2 : [ B>=21 ], cost: 1
4.40/2.19	
4.40/2.19	      4: f3 -> f300 : [], cost: 1
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Chained accelerated rules (with incoming rules):
4.40/2.19	
4.40/2.19	   Start location: f3
4.40/2.19	
4.40/2.19	      1: f2 -> f300 : B'=-1+B, [ 30>=A ], cost: 1
4.40/2.19	
4.40/2.19	      2: f300 -> f2 : [ B>=21 ], cost: 1
4.40/2.19	
4.40/2.19	      6: f300 -> f2 : A'=30, [ B>=21 && A>=31 ], cost: -29+A
4.40/2.19	
4.40/2.19	      4: f3 -> f300 : [], cost: 1
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Eliminated locations (on tree-shaped paths):
4.40/2.19	
4.40/2.19	   Start location: f3
4.40/2.19	
4.40/2.19	      7: f300 -> f300 : B'=-1+B, [ B>=21 && 30>=A ], cost: 2
4.40/2.19	
4.40/2.19	      8: f300 -> f300 : A'=30, B'=-1+B, [ B>=21 && A>=31 ], cost: -28+A
4.40/2.19	
4.40/2.19	      4: f3 -> f300 : [], cost: 1
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Accelerating simple loops of location 1.
4.40/2.19	
4.40/2.19	   Accelerating the following rules:
4.40/2.19	
4.40/2.19	      7: f300 -> f300 : B'=-1+B, [ B>=21 && 30>=A ], cost: 2
4.40/2.19	
4.40/2.19	      8: f300 -> f300 : A'=30, B'=-1+B, [ B>=21 && A>=31 ], cost: -28+A
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	   Accelerated rule 7 with metering function -20+B, yielding the new rule 9.
4.40/2.19	
4.40/2.19	   Found no metering function for rule 8.
4.40/2.19	
4.40/2.19	   Removing the simple loops: 7.
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Accelerated all simple loops using metering functions (where possible):
4.40/2.19	
4.40/2.19	   Start location: f3
4.40/2.19	
4.40/2.19	      8: f300 -> f300 : A'=30, B'=-1+B, [ B>=21 && A>=31 ], cost: -28+A
4.40/2.19	
4.40/2.19	      9: f300 -> f300 : B'=20, [ B>=21 && 30>=A ], cost: -40+2*B
4.40/2.19	
4.40/2.19	      4: f3 -> f300 : [], cost: 1
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Chained accelerated rules (with incoming rules):
4.40/2.19	
4.40/2.19	   Start location: f3
4.40/2.19	
4.40/2.19	      4: f3 -> f300 : [], cost: 1
4.40/2.19	
4.40/2.19	     10: f3 -> f300 : A'=30, B'=-1+B, [ B>=21 && A>=31 ], cost: -27+A
4.40/2.19	
4.40/2.19	     11: f3 -> f300 : B'=20, [ B>=21 && 30>=A ], cost: -39+2*B
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Removed unreachable locations (and leaf rules with constant cost):
4.40/2.19	
4.40/2.19	   Start location: f3
4.40/2.19	
4.40/2.19	     10: f3 -> f300 : A'=30, B'=-1+B, [ B>=21 && A>=31 ], cost: -27+A
4.40/2.19	
4.40/2.19	     11: f3 -> f300 : B'=20, [ B>=21 && 30>=A ], cost: -39+2*B
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	### Computing asymptotic complexity ###
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Fully simplified ITS problem
4.40/2.19	
4.40/2.19	   Start location: f3
4.40/2.19	
4.40/2.19	     10: f3 -> f300 : A'=30, B'=-1+B, [ B>=21 && A>=31 ], cost: -27+A
4.40/2.19	
4.40/2.19	     11: f3 -> f300 : B'=20, [ B>=21 && 30>=A ], cost: -39+2*B
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Computing asymptotic complexity for rule 10
4.40/2.19	
4.40/2.19	   Solved the limit problem by the following transformations:
4.40/2.19	
4.40/2.19	      Created initial limit problem:
4.40/2.19	
4.40/2.19	      -27+A (+), -20+B (+/+!), -30+A (+/+!) [not solved]
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	      removing all constraints (solved by SMT)
4.40/2.19	
4.40/2.19	      resulting limit problem: [solved]
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	      applying transformation rule (C) using substitution {A==n,B==n}
4.40/2.19	
4.40/2.19	      resulting limit problem:
4.40/2.19	
4.40/2.19	      [solved]
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	   Solution:
4.40/2.19	
4.40/2.19	      A / n
4.40/2.19	
4.40/2.19	      B / n
4.40/2.19	
4.40/2.19	   Resulting cost -27+n has complexity: Poly(n^1)
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Found new complexity Poly(n^1).
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	Obtained the following overall complexity (w.r.t. the length of the input n):
4.40/2.19	
4.40/2.19	   Complexity:  Poly(n^1)
4.40/2.19	
4.40/2.19	   Cpx degree:  1
4.40/2.19	
4.40/2.19	   Solved cost: -27+n
4.40/2.19	
4.40/2.19	   Rule cost:   -27+A
4.40/2.19	
4.40/2.19	   Rule guard:  [ B>=21 && A>=31 ]
4.40/2.19	
4.40/2.19	
4.40/2.19	
4.40/2.19	WORST_CASE(Omega(n^1),?)
4.40/2.19	
4.40/2.19	
4.40/2.19	----------------------------------------
4.40/2.19	
4.40/2.19	(4)
4.40/2.19	BOUNDS(n^1, INF)
4.40/2.20	EOF