9.85/6.33	WORST_CASE(Omega(n^2), ?)
9.85/6.34	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
9.85/6.34	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
9.85/6.34	
9.85/6.34	
9.85/6.34	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, INF).
9.85/6.34	
9.85/6.34	(0) CpxIntTrs
9.85/6.34	(1) Loat Proof [FINISHED, 1118 ms]
9.85/6.34	(2) BOUNDS(n^2, INF)
9.85/6.34	
9.85/6.34	
9.85/6.34	----------------------------------------
9.85/6.34	
9.85/6.34	(0)
9.85/6.34	Obligation:
9.85/6.34	Complexity Int TRS consisting of the following rules:
9.85/6.34	f1(A, B) -> Com_1(f2(A - 1, B)) :|: A >= 1
9.85/6.34	f2(A, B) -> Com_1(f2(A - 1, B + 1)) :|: A >= 1
9.85/6.34	f999(A, B) -> Com_1(f1(1, B - 1)) :|: B >= 1 && A >= 0 && A <= 0
9.85/6.34	f1(A, B) -> Com_1(f1(A + 1, B - 1)) :|: B >= 1
9.85/6.34	f2(A, B) -> Com_1(f1(A + 1, B - 1)) :|: B >= 1
9.85/6.34	
9.85/6.34	The start-symbols are:[f999_2]
9.85/6.34	
9.85/6.34	
9.85/6.34	----------------------------------------
9.85/6.34	
9.85/6.34	(1) Loat Proof (FINISHED)
9.85/6.34	
9.85/6.34	
9.85/6.34	### Pre-processing the ITS problem ###
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Initial linear ITS problem
9.85/6.34	
9.85/6.34	   Start location: f999
9.85/6.34	
9.85/6.34	      0: f1 -> f2 : A'=-1+A, [ A>=1 ], cost: 1
9.85/6.34	
9.85/6.34	      3: f1 -> f1 : A'=1+A, B'=-1+B, [ B>=1 ], cost: 1
9.85/6.34	
9.85/6.34	      1: f2 -> f2 : A'=-1+A, B'=1+B, [ A>=1 ], cost: 1
9.85/6.34	
9.85/6.34	      4: f2 -> f1 : A'=1+A, B'=-1+B, [ B>=1 ], cost: 1
9.85/6.34	
9.85/6.34	      2: f999 -> f1 : A'=1, B'=-1+B, [ B>=1 && A==0 ], cost: 1
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	### Simplification by acceleration and chaining ###
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Accelerating simple loops of location 0.
9.85/6.34	
9.85/6.34	   Accelerating the following rules:
9.85/6.34	
9.85/6.34	      3: f1 -> f1 : A'=1+A, B'=-1+B, [ B>=1 ], cost: 1
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	   Accelerated rule 3 with metering function B, yielding the new rule 5.
9.85/6.34	
9.85/6.34	   Removing the simple loops: 3.
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Accelerating simple loops of location 1.
9.85/6.34	
9.85/6.34	   Accelerating the following rules:
9.85/6.34	
9.85/6.34	      1: f2 -> f2 : A'=-1+A, B'=1+B, [ A>=1 ], cost: 1
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	   Accelerated rule 1 with metering function A, yielding the new rule 6.
9.85/6.34	
9.85/6.34	   Removing the simple loops: 1.
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Accelerated all simple loops using metering functions (where possible):
9.85/6.34	
9.85/6.34	   Start location: f999
9.85/6.34	
9.85/6.34	      0: f1 -> f2 : A'=-1+A, [ A>=1 ], cost: 1
9.85/6.34	
9.85/6.34	      5: f1 -> f1 : A'=A+B, B'=0, [ B>=1 ], cost: B
9.85/6.34	
9.85/6.34	      4: f2 -> f1 : A'=1+A, B'=-1+B, [ B>=1 ], cost: 1
9.85/6.34	
9.85/6.34	      6: f2 -> f2 : A'=0, B'=A+B, [ A>=1 ], cost: A
9.85/6.34	
9.85/6.34	      2: f999 -> f1 : A'=1, B'=-1+B, [ B>=1 && A==0 ], cost: 1
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Chained accelerated rules (with incoming rules):
9.85/6.34	
9.85/6.34	   Start location: f999
9.85/6.34	
9.85/6.34	      0: f1 -> f2 : A'=-1+A, [ A>=1 ], cost: 1
9.85/6.34	
9.85/6.34	      9: f1 -> f2 : A'=0, B'=-1+A+B, [ -1+A>=1 ], cost: A
9.85/6.34	
9.85/6.34	      4: f2 -> f1 : A'=1+A, B'=-1+B, [ B>=1 ], cost: 1
9.85/6.34	
9.85/6.34	      8: f2 -> f1 : A'=A+B, B'=0, [ -1+B>=1 ], cost: B
9.85/6.34	
9.85/6.34	      2: f999 -> f1 : A'=1, B'=-1+B, [ B>=1 && A==0 ], cost: 1
9.85/6.34	
9.85/6.34	      7: f999 -> f1 : A'=B, B'=0, [ A==0 && -1+B>=1 ], cost: B
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Eliminated locations (on tree-shaped paths):
9.85/6.34	
9.85/6.34	   Start location: f999
9.85/6.34	
9.85/6.34	     10: f1 -> f1 : A'=A, B'=-1+B, [ A>=1 && B>=1 ], cost: 2
9.85/6.34	
9.85/6.34	     11: f1 -> f1 : A'=-1+A+B, B'=0, [ A>=1 && -1+B>=1 ], cost: 1+B
9.85/6.34	
9.85/6.34	     12: f1 -> f1 : A'=1, B'=-2+A+B, [ -1+A>=1 && -1+A+B>=1 ], cost: 1+A
9.85/6.34	
9.85/6.34	     13: f1 -> f1 : A'=-1+A+B, B'=0, [ -1+A>=1 && -2+A+B>=1 ], cost: -1+2*A+B
9.85/6.34	
9.85/6.34	      2: f999 -> f1 : A'=1, B'=-1+B, [ B>=1 && A==0 ], cost: 1
9.85/6.34	
9.85/6.34	      7: f999 -> f1 : A'=B, B'=0, [ A==0 && -1+B>=1 ], cost: B
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Accelerating simple loops of location 0.
9.85/6.34	
9.85/6.34	   Simplified some of the simple loops (and removed duplicate rules).
9.85/6.34	
9.85/6.34	   Accelerating the following rules:
9.85/6.34	
9.85/6.34	     10: f1 -> f1 : B'=-1+B, [ A>=1 && B>=1 ], cost: 2
9.85/6.34	
9.85/6.34	     11: f1 -> f1 : A'=-1+A+B, B'=0, [ A>=1 && -1+B>=1 ], cost: 1+B
9.85/6.34	
9.85/6.34	     12: f1 -> f1 : A'=1, B'=-2+A+B, [ -1+A>=1 && -1+A+B>=1 ], cost: 1+A
9.85/6.34	
9.85/6.34	     13: f1 -> f1 : A'=-1+A+B, B'=0, [ -1+A>=1 && -2+A+B>=1 ], cost: -1+2*A+B
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	   Accelerated rule 10 with metering function B, yielding the new rule 14.
9.85/6.34	
9.85/6.34	   Found no metering function for rule 11.
9.85/6.34	
9.85/6.34	   Found no metering function for rule 12.
9.85/6.34	
9.85/6.34	   Accelerated rule 13 with metering function -2+A+B, yielding the new rule 15.
9.85/6.34	
9.85/6.34	   Removing the simple loops: 10 13.
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Accelerated all simple loops using metering functions (where possible):
9.85/6.34	
9.85/6.34	   Start location: f999
9.85/6.34	
9.85/6.34	     11: f1 -> f1 : A'=-1+A+B, B'=0, [ A>=1 && -1+B>=1 ], cost: 1+B
9.85/6.34	
9.85/6.34	     12: f1 -> f1 : A'=1, B'=-2+A+B, [ -1+A>=1 && -1+A+B>=1 ], cost: 1+A
9.85/6.34	
9.85/6.34	     14: f1 -> f1 : B'=0, [ A>=1 && B>=1 ], cost: 2*B
9.85/6.34	
9.85/6.34	     15: f1 -> f1 : A'=2-B, B'=0, [ -1+A>=1 && -2+A+B>=1 ], cost: 2*(-2+A+B)*A-(-2+A+B)^2
9.85/6.34	
9.85/6.34	      2: f999 -> f1 : A'=1, B'=-1+B, [ B>=1 && A==0 ], cost: 1
9.85/6.34	
9.85/6.34	      7: f999 -> f1 : A'=B, B'=0, [ A==0 && -1+B>=1 ], cost: B
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Chained accelerated rules (with incoming rules):
9.85/6.34	
9.85/6.34	   Start location: f999
9.85/6.34	
9.85/6.34	      2: f999 -> f1 : A'=1, B'=-1+B, [ B>=1 && A==0 ], cost: 1
9.85/6.34	
9.85/6.34	      7: f999 -> f1 : A'=B, B'=0, [ A==0 && -1+B>=1 ], cost: B
9.85/6.34	
9.85/6.34	     16: f999 -> f1 : A'=-1+B, B'=0, [ A==0 && -2+B>=1 ], cost: 1+B
9.85/6.34	
9.85/6.34	     17: f999 -> f1 : A'=1, B'=-2+B, [ A==0 && -1+B>=1 ], cost: 1+2*B
9.85/6.34	
9.85/6.34	     18: f999 -> f1 : A'=1, B'=0, [ A==0 && -1+B>=1 ], cost: -1+2*B
9.85/6.34	
9.85/6.34	     19: f999 -> f1 : A'=2, B'=0, [ A==0 && -2+B>=1 ], cost: -(-2+B)^2+2*(-2+B)*B+B
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Removed unreachable locations (and leaf rules with constant cost):
9.85/6.34	
9.85/6.34	   Start location: f999
9.85/6.34	
9.85/6.34	      7: f999 -> f1 : A'=B, B'=0, [ A==0 && -1+B>=1 ], cost: B
9.85/6.34	
9.85/6.34	     16: f999 -> f1 : A'=-1+B, B'=0, [ A==0 && -2+B>=1 ], cost: 1+B
9.85/6.34	
9.85/6.34	     17: f999 -> f1 : A'=1, B'=-2+B, [ A==0 && -1+B>=1 ], cost: 1+2*B
9.85/6.34	
9.85/6.34	     18: f999 -> f1 : A'=1, B'=0, [ A==0 && -1+B>=1 ], cost: -1+2*B
9.85/6.34	
9.85/6.34	     19: f999 -> f1 : A'=2, B'=0, [ A==0 && -2+B>=1 ], cost: -(-2+B)^2+2*(-2+B)*B+B
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	### Computing asymptotic complexity ###
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Fully simplified ITS problem
9.85/6.34	
9.85/6.34	   Start location: f999
9.85/6.34	
9.85/6.34	      7: f999 -> f1 : A'=B, B'=0, [ A==0 && -1+B>=1 ], cost: B
9.85/6.34	
9.85/6.34	     16: f999 -> f1 : A'=-1+B, B'=0, [ A==0 && -2+B>=1 ], cost: 1+B
9.85/6.34	
9.85/6.34	     17: f999 -> f1 : A'=1, B'=-2+B, [ A==0 && -1+B>=1 ], cost: 1+2*B
9.85/6.34	
9.85/6.34	     19: f999 -> f1 : A'=2, B'=0, [ A==0 && -2+B>=1 ], cost: -(-2+B)^2+2*(-2+B)*B+B
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Computing asymptotic complexity for rule 7
9.85/6.34	
9.85/6.34	   Solved the limit problem by the following transformations:
9.85/6.34	
9.85/6.34	      Created initial limit problem:
9.85/6.34	
9.85/6.34	      1-A (+/+!), -1+B (+/+!), B (+), 1+A (+/+!) [not solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	      applying transformation rule (C) using substitution {A==0}
9.85/6.34	
9.85/6.34	      resulting limit problem:
9.85/6.34	
9.85/6.34	      1 (+/+!), -1+B (+/+!), B (+) [not solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	      applying transformation rule (B), deleting 1 (+/+!)
9.85/6.34	
9.85/6.34	      resulting limit problem:
9.85/6.34	
9.85/6.34	      -1+B (+/+!), B (+) [not solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	      removing all constraints (solved by SMT)
9.85/6.34	
9.85/6.34	      resulting limit problem: [solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	      applying transformation rule (C) using substitution {B==n}
9.85/6.34	
9.85/6.34	      resulting limit problem:
9.85/6.34	
9.85/6.34	      [solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	   Solution:
9.85/6.34	
9.85/6.34	      A / 0
9.85/6.34	
9.85/6.34	      B / n
9.85/6.34	
9.85/6.34	   Resulting cost n has complexity: Poly(n^1)
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Found new complexity Poly(n^1).
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Computing asymptotic complexity for rule 19
9.85/6.34	
9.85/6.34	   Solved the limit problem by the following transformations:
9.85/6.34	
9.85/6.34	      Created initial limit problem:
9.85/6.34	
9.85/6.34	      -4+B^2+B (+), 1-A (+/+!), -2+B (+/+!), 1+A (+/+!) [not solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	      applying transformation rule (C) using substitution {A==0}
9.85/6.34	
9.85/6.34	      resulting limit problem:
9.85/6.34	
9.85/6.34	      1 (+/+!), -4+B^2+B (+), -2+B (+/+!) [not solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	      applying transformation rule (B), deleting 1 (+/+!)
9.85/6.34	
9.85/6.34	      resulting limit problem:
9.85/6.34	
9.85/6.34	      -4+B^2+B (+), -2+B (+/+!) [not solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	      removing all constraints (solved by SMT)
9.85/6.34	
9.85/6.34	      resulting limit problem: [solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	      applying transformation rule (C) using substitution {B==n}
9.85/6.34	
9.85/6.34	      resulting limit problem:
9.85/6.34	
9.85/6.34	      [solved]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	   Solution:
9.85/6.34	
9.85/6.34	      A / 0
9.85/6.34	
9.85/6.34	      B / n
9.85/6.34	
9.85/6.34	   Resulting cost -4+n^2+n has complexity: Poly(n^2)
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Found new complexity Poly(n^2).
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	Obtained the following overall complexity (w.r.t. the length of the input n):
9.85/6.34	
9.85/6.34	   Complexity:  Poly(n^2)
9.85/6.34	
9.85/6.34	   Cpx degree:  2
9.85/6.34	
9.85/6.34	   Solved cost: -4+n^2+n
9.85/6.34	
9.85/6.34	   Rule cost:   -(-2+B)^2+2*(-2+B)*B+B
9.85/6.34	
9.85/6.34	   Rule guard:  [ A==0 && -2+B>=1 ]
9.85/6.34	
9.85/6.34	
9.85/6.34	
9.85/6.34	WORST_CASE(Omega(n^2),?)
9.85/6.34	
9.85/6.34	
9.85/6.34	----------------------------------------
9.85/6.34	
9.85/6.34	(2)
9.85/6.34	BOUNDS(n^2, INF)
9.85/6.37	EOF