3.97/1.94	WORST_CASE(Omega(n^2), O(n^2))
3.97/1.95	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
3.97/1.95	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.97/1.95	
3.97/1.95	
3.97/1.95	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, n^2).
3.97/1.95	
3.97/1.95	(0) CpxIntTrs
3.97/1.95	(1) Koat Proof [FINISHED, 9 ms]
3.97/1.95	(2) BOUNDS(1, n^2)
3.97/1.95	(3) Loat Proof [FINISHED, 324 ms]
3.97/1.95	(4) BOUNDS(n^2, INF)
3.97/1.95	
3.97/1.95	
3.97/1.95	----------------------------------------
3.97/1.95	
3.97/1.95	(0)
3.97/1.95	Obligation:
3.97/1.95	Complexity Int TRS consisting of the following rules:
3.97/1.95	eval1(A, B) -> Com_1(eval2(A + 1, 1)) :|: A >= 0
3.97/1.95	eval2(A, B) -> Com_1(eval2(A, B + 1)) :|: A >= 0 && B >= 1 && A >= B
3.97/1.95	eval2(A, B) -> Com_1(eval1(A - 2, B)) :|: A >= 0 && B >= 1 && B >= A + 1
3.97/1.95	start(A, B) -> Com_1(eval1(A, B)) :|: TRUE
3.97/1.95	
3.97/1.95	The start-symbols are:[start_2]
3.97/1.95	
3.97/1.95	
3.97/1.95	----------------------------------------
3.97/1.95	
3.97/1.95	(1) Koat Proof (FINISHED)
3.97/1.95	YES(?, 128*ar_0 + 6*ar_0^2 + 233)
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Initial complexity problem:
3.97/1.95	
3.97/1.95	1:	T:
3.97/1.95	
3.97/1.95			(Comp: ?, Cost: 1)    eval1(ar_0, ar_1) -> Com_1(eval2(ar_0 + 1, 1)) [ ar_0 >= 0 ]
3.97/1.95	
3.97/1.95			(Comp: ?, Cost: 1)    eval2(ar_0, ar_1) -> Com_1(eval2(ar_0, ar_1 + 1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_0 >= ar_1 ]
3.97/1.95	
3.97/1.95			(Comp: ?, Cost: 1)    eval2(ar_0, ar_1) -> Com_1(eval1(ar_0 - 2, ar_1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_1 >= ar_0 + 1 ]
3.97/1.95	
3.97/1.95			(Comp: ?, Cost: 1)    start(ar_0, ar_1) -> Com_1(eval1(ar_0, ar_1))
3.97/1.95	
3.97/1.95			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(start(ar_0, ar_1)) [ 0 <= 0 ]
3.97/1.95	
3.97/1.95		start location:	koat_start
3.97/1.95	
3.97/1.95		leaf cost:	0
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Repeatedly propagating knowledge in problem 1 produces the following problem:
3.97/1.95	
3.97/1.95	2:	T:
3.97/1.95	
3.97/1.95			(Comp: ?, Cost: 1)    eval1(ar_0, ar_1) -> Com_1(eval2(ar_0 + 1, 1)) [ ar_0 >= 0 ]
3.97/1.95	
3.97/1.95			(Comp: ?, Cost: 1)    eval2(ar_0, ar_1) -> Com_1(eval2(ar_0, ar_1 + 1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_0 >= ar_1 ]
3.97/1.95	
3.97/1.95			(Comp: ?, Cost: 1)    eval2(ar_0, ar_1) -> Com_1(eval1(ar_0 - 2, ar_1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_1 >= ar_0 + 1 ]
3.97/1.95	
3.97/1.95			(Comp: 1, Cost: 1)    start(ar_0, ar_1) -> Com_1(eval1(ar_0, ar_1))
3.97/1.95	
3.97/1.95			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(start(ar_0, ar_1)) [ 0 <= 0 ]
3.97/1.95	
3.97/1.95		start location:	koat_start
3.97/1.95	
3.97/1.95		leaf cost:	0
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	A polynomial rank function with
3.97/1.95	
3.97/1.95		Pol(eval1) = 2*V_1 + 4
3.97/1.95	
3.97/1.95		Pol(eval2) = 2*V_1 + 1
3.97/1.95	
3.97/1.95		Pol(start) = 2*V_1 + 4
3.97/1.95	
3.97/1.95		Pol(koat_start) = 2*V_1 + 4
3.97/1.95	
3.97/1.95	orients all transitions weakly and the transitions
3.97/1.95	
3.97/1.95		eval2(ar_0, ar_1) -> Com_1(eval1(ar_0 - 2, ar_1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_1 >= ar_0 + 1 ]
3.97/1.95	
3.97/1.95		eval1(ar_0, ar_1) -> Com_1(eval2(ar_0 + 1, 1)) [ ar_0 >= 0 ]
3.97/1.95	
3.97/1.95	strictly and produces the following problem:
3.97/1.95	
3.97/1.95	3:	T:
3.97/1.95	
3.97/1.95			(Comp: 2*ar_0 + 4, Cost: 1)    eval1(ar_0, ar_1) -> Com_1(eval2(ar_0 + 1, 1)) [ ar_0 >= 0 ]
3.97/1.95	
3.97/1.95			(Comp: ?, Cost: 1)             eval2(ar_0, ar_1) -> Com_1(eval2(ar_0, ar_1 + 1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_0 >= ar_1 ]
3.97/1.95	
3.97/1.95			(Comp: 2*ar_0 + 4, Cost: 1)    eval2(ar_0, ar_1) -> Com_1(eval1(ar_0 - 2, ar_1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_1 >= ar_0 + 1 ]
3.97/1.95	
3.97/1.95			(Comp: 1, Cost: 1)             start(ar_0, ar_1) -> Com_1(eval1(ar_0, ar_1))
3.97/1.95	
3.97/1.95			(Comp: 1, Cost: 0)             koat_start(ar_0, ar_1) -> Com_1(start(ar_0, ar_1)) [ 0 <= 0 ]
3.97/1.95	
3.97/1.95		start location:	koat_start
3.97/1.95	
3.97/1.95		leaf cost:	0
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	A polynomial rank function with
3.97/1.95	
3.97/1.95		Pol(eval2) = V_1 - V_2 + 1
3.97/1.95	
3.97/1.95	and size complexities
3.97/1.95	
3.97/1.95		S("koat_start(ar_0, ar_1) -> Com_1(start(ar_0, ar_1)) [ 0 <= 0 ]", 0-0) = ar_0
3.97/1.95	
3.97/1.95		S("koat_start(ar_0, ar_1) -> Com_1(start(ar_0, ar_1)) [ 0 <= 0 ]", 0-1) = ar_1
3.97/1.95	
3.97/1.95		S("start(ar_0, ar_1) -> Com_1(eval1(ar_0, ar_1))", 0-0) = ar_0
3.97/1.95	
3.97/1.95		S("start(ar_0, ar_1) -> Com_1(eval1(ar_0, ar_1))", 0-1) = ar_1
3.97/1.95	
3.97/1.95		S("eval2(ar_0, ar_1) -> Com_1(eval1(ar_0 - 2, ar_1)) [ ar_0 >= 0 /\\ ar_1 >= 1 /\\ ar_1 >= ar_0 + 1 ]", 0-0) = 3*ar_0 + 54
3.97/1.95	
3.97/1.95		S("eval2(ar_0, ar_1) -> Com_1(eval1(ar_0 - 2, ar_1)) [ ar_0 >= 0 /\\ ar_1 >= 1 /\\ ar_1 >= ar_0 + 1 ]", 0-1) = ?
3.97/1.95	
3.97/1.95		S("eval2(ar_0, ar_1) -> Com_1(eval2(ar_0, ar_1 + 1)) [ ar_0 >= 0 /\\ ar_1 >= 1 /\\ ar_0 >= ar_1 ]", 0-0) = 3*ar_0 + 54
3.97/1.95	
3.97/1.95		S("eval2(ar_0, ar_1) -> Com_1(eval2(ar_0, ar_1 + 1)) [ ar_0 >= 0 /\\ ar_1 >= 1 /\\ ar_0 >= ar_1 ]", 0-1) = ?
3.97/1.95	
3.97/1.95		S("eval1(ar_0, ar_1) -> Com_1(eval2(ar_0 + 1, 1)) [ ar_0 >= 0 ]", 0-0) = 3*ar_0 + 54
3.97/1.95	
3.97/1.95		S("eval1(ar_0, ar_1) -> Com_1(eval2(ar_0 + 1, 1)) [ ar_0 >= 0 ]", 0-1) = 1
3.97/1.95	
3.97/1.95	orients the transitions
3.97/1.95	
3.97/1.95		eval2(ar_0, ar_1) -> Com_1(eval2(ar_0, ar_1 + 1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_0 >= ar_1 ]
3.97/1.95	
3.97/1.95	weakly and the transition
3.97/1.95	
3.97/1.95		eval2(ar_0, ar_1) -> Com_1(eval2(ar_0, ar_1 + 1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_0 >= ar_1 ]
3.97/1.95	
3.97/1.95	strictly and produces the following problem:
3.97/1.95	
3.97/1.95	4:	T:
3.97/1.95	
3.97/1.95			(Comp: 2*ar_0 + 4, Cost: 1)                   eval1(ar_0, ar_1) -> Com_1(eval2(ar_0 + 1, 1)) [ ar_0 >= 0 ]
3.97/1.95	
3.97/1.95			(Comp: 6*ar_0^2 + 124*ar_0 + 224, Cost: 1)    eval2(ar_0, ar_1) -> Com_1(eval2(ar_0, ar_1 + 1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_0 >= ar_1 ]
3.97/1.95	
3.97/1.95			(Comp: 2*ar_0 + 4, Cost: 1)                   eval2(ar_0, ar_1) -> Com_1(eval1(ar_0 - 2, ar_1)) [ ar_0 >= 0 /\ ar_1 >= 1 /\ ar_1 >= ar_0 + 1 ]
3.97/1.95	
3.97/1.95			(Comp: 1, Cost: 1)                            start(ar_0, ar_1) -> Com_1(eval1(ar_0, ar_1))
3.97/1.95	
3.97/1.95			(Comp: 1, Cost: 0)                            koat_start(ar_0, ar_1) -> Com_1(start(ar_0, ar_1)) [ 0 <= 0 ]
3.97/1.95	
3.97/1.95		start location:	koat_start
3.97/1.95	
3.97/1.95		leaf cost:	0
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Complexity upper bound 128*ar_0 + 6*ar_0^2 + 233
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Time: 0.066 sec (SMT: 0.060 sec)
3.97/1.95	
3.97/1.95	
3.97/1.95	----------------------------------------
3.97/1.95	
3.97/1.95	(2)
3.97/1.95	BOUNDS(1, n^2)
3.97/1.95	
3.97/1.95	----------------------------------------
3.97/1.95	
3.97/1.95	(3) Loat Proof (FINISHED)
3.97/1.95	
3.97/1.95	
3.97/1.95	### Pre-processing the ITS problem ###
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Initial linear ITS problem
3.97/1.95	
3.97/1.95	   Start location: start
3.97/1.95	
3.97/1.95	      0: eval1 -> eval2 : A'=1+A, B'=1, [ A>=0 ], cost: 1
3.97/1.95	
3.97/1.95	      1: eval2 -> eval2 : B'=1+B, [ A>=0 && B>=1 && A>=B ], cost: 1
3.97/1.95	
3.97/1.95	      2: eval2 -> eval1 : A'=-2+A, [ A>=0 && B>=1 && B>=1+A ], cost: 1
3.97/1.95	
3.97/1.95	      3: start -> eval1 : [], cost: 1
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Simplified all rules, resulting in:
3.97/1.95	
3.97/1.95	   Start location: start
3.97/1.95	
3.97/1.95	      0: eval1 -> eval2 : A'=1+A, B'=1, [ A>=0 ], cost: 1
3.97/1.95	
3.97/1.95	      1: eval2 -> eval2 : B'=1+B, [ B>=1 && A>=B ], cost: 1
3.97/1.95	
3.97/1.95	      2: eval2 -> eval1 : A'=-2+A, [ A>=0 && B>=1 && B>=1+A ], cost: 1
3.97/1.95	
3.97/1.95	      3: start -> eval1 : [], cost: 1
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	### Simplification by acceleration and chaining ###
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Accelerating simple loops of location 1.
3.97/1.95	
3.97/1.95	   Accelerating the following rules:
3.97/1.95	
3.97/1.95	      1: eval2 -> eval2 : B'=1+B, [ B>=1 && A>=B ], cost: 1
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	   Accelerated rule 1 with metering function 1+A-B, yielding the new rule 4.
3.97/1.95	
3.97/1.95	   Removing the simple loops: 1.
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Accelerated all simple loops using metering functions (where possible):
3.97/1.95	
3.97/1.95	   Start location: start
3.97/1.95	
3.97/1.95	      0: eval1 -> eval2 : A'=1+A, B'=1, [ A>=0 ], cost: 1
3.97/1.95	
3.97/1.95	      2: eval2 -> eval1 : A'=-2+A, [ A>=0 && B>=1 && B>=1+A ], cost: 1
3.97/1.95	
3.97/1.95	      4: eval2 -> eval2 : B'=1+A, [ B>=1 && A>=B ], cost: 1+A-B
3.97/1.95	
3.97/1.95	      3: start -> eval1 : [], cost: 1
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Chained accelerated rules (with incoming rules):
3.97/1.95	
3.97/1.95	   Start location: start
3.97/1.95	
3.97/1.95	      0: eval1 -> eval2 : A'=1+A, B'=1, [ A>=0 ], cost: 1
3.97/1.95	
3.97/1.95	      5: eval1 -> eval2 : A'=1+A, B'=2+A, [ A>=0 ], cost: 2+A
3.97/1.95	
3.97/1.95	      2: eval2 -> eval1 : A'=-2+A, [ A>=0 && B>=1 && B>=1+A ], cost: 1
3.97/1.95	
3.97/1.95	      3: start -> eval1 : [], cost: 1
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Eliminated locations (on tree-shaped paths):
3.97/1.95	
3.97/1.95	   Start location: start
3.97/1.95	
3.97/1.95	      6: eval1 -> eval1 : A'=-1+A, B'=2+A, [ A>=0 ], cost: 3+A
3.97/1.95	
3.97/1.95	      3: start -> eval1 : [], cost: 1
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Accelerating simple loops of location 0.
3.97/1.95	
3.97/1.95	   Accelerating the following rules:
3.97/1.95	
3.97/1.95	      6: eval1 -> eval1 : A'=-1+A, B'=2+A, [ A>=0 ], cost: 3+A
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	   Accelerated rule 6 with metering function 1+A, yielding the new rule 7.
3.97/1.95	
3.97/1.95	   Removing the simple loops: 6.
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Accelerated all simple loops using metering functions (where possible):
3.97/1.95	
3.97/1.95	   Start location: start
3.97/1.95	
3.97/1.95	      7: eval1 -> eval1 : A'=-1, B'=2, [ A>=0 ], cost: 7/2-1/2*(1+A)^2+7/2*A+A*(1+A)
3.97/1.95	
3.97/1.95	      3: start -> eval1 : [], cost: 1
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Chained accelerated rules (with incoming rules):
3.97/1.95	
3.97/1.95	   Start location: start
3.97/1.95	
3.97/1.95	      3: start -> eval1 : [], cost: 1
3.97/1.95	
3.97/1.95	      8: start -> eval1 : A'=-1, B'=2, [ A>=0 ], cost: 9/2-1/2*(1+A)^2+7/2*A+A*(1+A)
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Removed unreachable locations (and leaf rules with constant cost):
3.97/1.95	
3.97/1.95	   Start location: start
3.97/1.95	
3.97/1.95	      8: start -> eval1 : A'=-1, B'=2, [ A>=0 ], cost: 9/2-1/2*(1+A)^2+7/2*A+A*(1+A)
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	### Computing asymptotic complexity ###
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Fully simplified ITS problem
3.97/1.95	
3.97/1.95	   Start location: start
3.97/1.95	
3.97/1.95	      8: start -> eval1 : A'=-1, B'=2, [ A>=0 ], cost: 9/2-1/2*(1+A)^2+7/2*A+A*(1+A)
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Computing asymptotic complexity for rule 8
3.97/1.95	
3.97/1.95	   Solved the limit problem by the following transformations:
3.97/1.95	
3.97/1.95	      Created initial limit problem:
3.97/1.95	
3.97/1.95	      4+7/2*A+1/2*A^2 (+), 1+A (+/+!) [not solved]
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	      removing all constraints (solved by SMT)
3.97/1.95	
3.97/1.95	      resulting limit problem: [solved]
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	      applying transformation rule (C) using substitution {A==n}
3.97/1.95	
3.97/1.95	      resulting limit problem:
3.97/1.95	
3.97/1.95	      [solved]
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	   Solution:
3.97/1.95	
3.97/1.95	      A / n
3.97/1.95	
3.97/1.95	   Resulting cost 4+1/2*n^2+7/2*n has complexity: Poly(n^2)
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Found new complexity Poly(n^2).
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	Obtained the following overall complexity (w.r.t. the length of the input n):
3.97/1.95	
3.97/1.95	   Complexity:  Poly(n^2)
3.97/1.95	
3.97/1.95	   Cpx degree:  2
3.97/1.95	
3.97/1.95	   Solved cost: 4+1/2*n^2+7/2*n
3.97/1.95	
3.97/1.95	   Rule cost:   9/2-1/2*(1+A)^2+7/2*A+A*(1+A)
3.97/1.95	
3.97/1.95	   Rule guard:  [ A>=0 ]
3.97/1.95	
3.97/1.95	
3.97/1.95	
3.97/1.95	WORST_CASE(Omega(n^2),?)
3.97/1.95	
3.97/1.95	
3.97/1.95	----------------------------------------
3.97/1.95	
3.97/1.95	(4)
3.97/1.95	BOUNDS(n^2, INF)
3.97/1.97	EOF