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