4.79/2.22	WORST_CASE(Omega(n^1), O(n^1))
4.79/2.23	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.79/2.23	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.79/2.23	
4.79/2.23	
4.79/2.23	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1).
4.79/2.23	
4.79/2.23	(0) CpxIntTrs
4.79/2.23	(1) Koat Proof [FINISHED, 236 ms]
4.79/2.23	(2) BOUNDS(1, n^1)
4.79/2.23	(3) Loat Proof [FINISHED, 516 ms]
4.79/2.23	(4) BOUNDS(n^1, INF)
4.79/2.23	
4.79/2.23	
4.79/2.23	----------------------------------------
4.79/2.23	
4.79/2.23	(0)
4.79/2.23	Obligation:
4.79/2.23	Complexity Int TRS consisting of the following rules:
4.79/2.23	evalDis1start(A, B, C, D) -> Com_1(evalDis1entryin(A, B, C, D)) :|: TRUE
4.79/2.23	evalDis1entryin(A, B, C, D) -> Com_1(evalDis1bb3in(B, A, D, C)) :|: TRUE
4.79/2.23	evalDis1bb3in(A, B, C, D) -> Com_1(evalDis1bbin(A, B, C, D)) :|: A >= B + 1
4.79/2.23	evalDis1bb3in(A, B, C, D) -> Com_1(evalDis1returnin(A, B, C, D)) :|: B >= A
4.79/2.23	evalDis1bbin(A, B, C, D) -> Com_1(evalDis1bb1in(A, B, C, D)) :|: C >= D + 1
4.79/2.23	evalDis1bbin(A, B, C, D) -> Com_1(evalDis1bb2in(A, B, C, D)) :|: D >= C
4.79/2.23	evalDis1bb1in(A, B, C, D) -> Com_1(evalDis1bb3in(A, B, C, D + 1)) :|: TRUE
4.79/2.23	evalDis1bb2in(A, B, C, D) -> Com_1(evalDis1bb3in(A, B + 1, C, D)) :|: TRUE
4.79/2.23	evalDis1returnin(A, B, C, D) -> Com_1(evalDis1stop(A, B, C, D)) :|: TRUE
4.79/2.23	
4.79/2.23	The start-symbols are:[evalDis1start_4]
4.79/2.23	
4.79/2.23	
4.79/2.23	----------------------------------------
4.79/2.23	
4.79/2.23	(1) Koat Proof (FINISHED)
4.79/2.23	YES(?, 6*ar_0 + 6*ar_1 + 3*ar_2 + 3*ar_3 + 10)
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Initial complexity problem:
4.79/2.23	
4.79/2.23	1:	T:
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1entryin(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_1, ar_0, ar_3, ar_2))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bbin(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1returnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_3 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= ar_2 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1, ar_2, ar_3 + 1))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1 + 1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1stop(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.79/2.23	
4.79/2.23		start location:	koat_start
4.79/2.23	
4.79/2.23		leaf cost:	0
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Repeatedly propagating knowledge in problem 1 produces the following problem:
4.79/2.23	
4.79/2.23	2:	T:
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)    evalDis1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1entryin(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)    evalDis1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_1, ar_0, ar_3, ar_2))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bbin(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1returnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_3 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= ar_2 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1, ar_2, ar_3 + 1))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1 + 1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1stop(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.79/2.23	
4.79/2.23		start location:	koat_start
4.79/2.23	
4.79/2.23		leaf cost:	0
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	A polynomial rank function with
4.79/2.23	
4.79/2.23		Pol(evalDis1start) = 2
4.79/2.23	
4.79/2.23		Pol(evalDis1entryin) = 2
4.79/2.23	
4.79/2.23		Pol(evalDis1bb3in) = 2
4.79/2.23	
4.79/2.23		Pol(evalDis1bbin) = 2
4.79/2.23	
4.79/2.23		Pol(evalDis1returnin) = 1
4.79/2.23	
4.79/2.23		Pol(evalDis1bb1in) = 2
4.79/2.23	
4.79/2.23		Pol(evalDis1bb2in) = 2
4.79/2.23	
4.79/2.23		Pol(evalDis1stop) = 0
4.79/2.23	
4.79/2.23		Pol(koat_start) = 2
4.79/2.23	
4.79/2.23	orients all transitions weakly and the transitions
4.79/2.23	
4.79/2.23		evalDis1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1stop(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23		evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1returnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ]
4.79/2.23	
4.79/2.23	strictly and produces the following problem:
4.79/2.23	
4.79/2.23	3:	T:
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)    evalDis1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1entryin(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)    evalDis1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_1, ar_0, ar_3, ar_2))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bbin(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)    evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1returnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_3 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= ar_2 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1, ar_2, ar_3 + 1))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)    evalDis1bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1 + 1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)    evalDis1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1stop(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.79/2.23	
4.79/2.23		start location:	koat_start
4.79/2.23	
4.79/2.23		leaf cost:	0
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	A polynomial rank function with
4.79/2.23	
4.79/2.23		Pol(evalDis1start) = -V_3 + V_4 + 1
4.79/2.23	
4.79/2.23		Pol(evalDis1entryin) = -V_3 + V_4 + 1
4.79/2.23	
4.79/2.23		Pol(evalDis1bb3in) = V_3 - V_4 + 1
4.79/2.23	
4.79/2.23		Pol(evalDis1bbin) = V_3 - V_4 + 1
4.79/2.23	
4.79/2.23		Pol(evalDis1returnin) = V_3 - V_4
4.79/2.23	
4.79/2.23		Pol(evalDis1bb1in) = V_3 - V_4
4.79/2.23	
4.79/2.23		Pol(evalDis1bb2in) = V_3 - V_4 + 1
4.79/2.23	
4.79/2.23		Pol(evalDis1stop) = V_3 - V_4
4.79/2.23	
4.79/2.23		Pol(koat_start) = -V_3 + V_4 + 1
4.79/2.23	
4.79/2.23	orients all transitions weakly and the transition
4.79/2.23	
4.79/2.23		evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_3 + 1 ]
4.79/2.23	
4.79/2.23	strictly and produces the following problem:
4.79/2.23	
4.79/2.23	4:	T:
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                  evalDis1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1entryin(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                  evalDis1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_1, ar_0, ar_3, ar_2))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bbin(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                  evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1returnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 1, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_3 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= ar_2 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1, ar_2, ar_3 + 1))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1 + 1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                  evalDis1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1stop(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 0)                  koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.79/2.23	
4.79/2.23		start location:	koat_start
4.79/2.23	
4.79/2.23		leaf cost:	0
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Repeatedly propagating knowledge in problem 4 produces the following problem:
4.79/2.23	
4.79/2.23	5:	T:
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                  evalDis1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1entryin(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                  evalDis1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_1, ar_0, ar_3, ar_2))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bbin(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                  evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1returnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 1, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_3 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= ar_2 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 1, Cost: 1)    evalDis1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1, ar_2, ar_3 + 1))
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1 + 1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                  evalDis1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1stop(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 0)                  koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.79/2.23	
4.79/2.23		start location:	koat_start
4.79/2.23	
4.79/2.23		leaf cost:	0
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Applied AI with 'oct' on problem 5 to obtain the following invariants:
4.79/2.23	
4.79/2.23	  For symbol evalDis1bb1in: X_3 - X_4 - 1 >= 0 /\ X_1 - X_2 - 1 >= 0
4.79/2.23	
4.79/2.23	  For symbol evalDis1bb2in: -X_3 + X_4 >= 0 /\ X_1 - X_2 - 1 >= 0
4.79/2.23	
4.79/2.23	  For symbol evalDis1bbin: X_1 - X_2 - 1 >= 0
4.79/2.23	
4.79/2.23	  For symbol evalDis1returnin: -X_1 + X_2 >= 0
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	This yielded the following problem:
4.79/2.23	
4.79/2.23	6:	T:
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 0)                  koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                  evalDis1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_0 + ar_1 >= 0 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1 + 1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ ar_0 - ar_1 - 1 >= 0 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 1, Cost: 1)    evalDis1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1, ar_2, ar_3 + 1)) [ ar_2 - ar_3 - 1 >= 0 /\ ar_0 - ar_1 - 1 >= 0 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_3 >= ar_2 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 1, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_2 >= ar_3 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                  evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1returnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bbin(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                  evalDis1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_1, ar_0, ar_3, ar_2))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                  evalDis1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1entryin(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23		start location:	koat_start
4.79/2.23	
4.79/2.23		leaf cost:	0
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	A polynomial rank function with
4.79/2.23	
4.79/2.23		Pol(koat_start) = -2*V_1 + 2*V_2
4.79/2.23	
4.79/2.23		Pol(evalDis1start) = -2*V_1 + 2*V_2
4.79/2.23	
4.79/2.23		Pol(evalDis1returnin) = 2*V_1 - 2*V_2
4.79/2.23	
4.79/2.23		Pol(evalDis1stop) = 2*V_1 - 2*V_2
4.79/2.23	
4.79/2.23		Pol(evalDis1bb2in) = 2*V_1 - 2*V_2 - 1
4.79/2.23	
4.79/2.23		Pol(evalDis1bb3in) = 2*V_1 - 2*V_2
4.79/2.23	
4.79/2.23		Pol(evalDis1bb1in) = 2*V_1 - 2*V_2
4.79/2.23	
4.79/2.23		Pol(evalDis1bbin) = 2*V_1 - 2*V_2
4.79/2.23	
4.79/2.23		Pol(evalDis1entryin) = -2*V_1 + 2*V_2
4.79/2.23	
4.79/2.23	orients all transitions weakly and the transitions
4.79/2.23	
4.79/2.23		evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_3 >= ar_2 ]
4.79/2.23	
4.79/2.23		evalDis1bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1 + 1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ ar_0 - ar_1 - 1 >= 0 ]
4.79/2.23	
4.79/2.23	strictly and produces the following problem:
4.79/2.23	
4.79/2.23	7:	T:
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 0)                  koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                  evalDis1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_0 + ar_1 >= 0 ]
4.79/2.23	
4.79/2.23			(Comp: 2*ar_0 + 2*ar_1, Cost: 1)    evalDis1bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1 + 1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ ar_0 - ar_1 - 1 >= 0 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 1, Cost: 1)    evalDis1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1, ar_2, ar_3 + 1)) [ ar_2 - ar_3 - 1 >= 0 /\ ar_0 - ar_1 - 1 >= 0 ]
4.79/2.23	
4.79/2.23			(Comp: 2*ar_0 + 2*ar_1, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_3 >= ar_2 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 1, Cost: 1)    evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_2 >= ar_3 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                  evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1returnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ]
4.79/2.23	
4.79/2.23			(Comp: ?, Cost: 1)                  evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bbin(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                  evalDis1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_1, ar_0, ar_3, ar_2))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                  evalDis1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1entryin(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23		start location:	koat_start
4.79/2.23	
4.79/2.23		leaf cost:	0
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Repeatedly propagating knowledge in problem 7 produces the following problem:
4.79/2.23	
4.79/2.23	8:	T:
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 0)                                    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                                    evalDis1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_0 + ar_1 >= 0 ]
4.79/2.23	
4.79/2.23			(Comp: 2*ar_0 + 2*ar_1, Cost: 1)                      evalDis1bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1 + 1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ ar_0 - ar_1 - 1 >= 0 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 1, Cost: 1)                      evalDis1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_0, ar_1, ar_2, ar_3 + 1)) [ ar_2 - ar_3 - 1 >= 0 /\ ar_0 - ar_1 - 1 >= 0 ]
4.79/2.23	
4.79/2.23			(Comp: 2*ar_0 + 2*ar_1, Cost: 1)                      evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_3 >= ar_2 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 1, Cost: 1)                      evalDis1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_2 >= ar_3 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: 2, Cost: 1)                                    evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1returnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ]
4.79/2.23	
4.79/2.23			(Comp: ar_2 + ar_3 + 2*ar_0 + 2*ar_1 + 2, Cost: 1)    evalDis1bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bbin(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 + 1 ]
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                                    evalDis1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1bb3in(ar_1, ar_0, ar_3, ar_2))
4.79/2.23	
4.79/2.23			(Comp: 1, Cost: 1)                                    evalDis1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalDis1entryin(ar_0, ar_1, ar_2, ar_3))
4.79/2.23	
4.79/2.23		start location:	koat_start
4.79/2.23	
4.79/2.23		leaf cost:	0
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Complexity upper bound 6*ar_0 + 6*ar_1 + 3*ar_2 + 3*ar_3 + 10
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Time: 0.219 sec (SMT: 0.187 sec)
4.79/2.23	
4.79/2.23	
4.79/2.23	----------------------------------------
4.79/2.23	
4.79/2.23	(2)
4.79/2.23	BOUNDS(1, n^1)
4.79/2.23	
4.79/2.23	----------------------------------------
4.79/2.23	
4.79/2.23	(3) Loat Proof (FINISHED)
4.79/2.23	
4.79/2.23	
4.79/2.23	### Pre-processing the ITS problem ###
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Initial linear ITS problem
4.79/2.23	
4.79/2.23	   Start location: evalDis1start
4.79/2.23	
4.79/2.23	      0: evalDis1start -> evalDis1entryin : [], cost: 1
4.79/2.23	
4.79/2.23	      1: evalDis1entryin -> evalDis1bb3in : A'=B, B'=A, C'=D, D'=C, [], cost: 1
4.79/2.23	
4.79/2.23	      2: evalDis1bb3in -> evalDis1bbin : [ A>=1+B ], cost: 1
4.79/2.23	
4.79/2.23	      3: evalDis1bb3in -> evalDis1returnin : [ B>=A ], cost: 1
4.79/2.23	
4.79/2.23	      4: evalDis1bbin -> evalDis1bb1in : [ C>=1+D ], cost: 1
4.79/2.23	
4.79/2.23	      5: evalDis1bbin -> evalDis1bb2in : [ D>=C ], cost: 1
4.79/2.23	
4.79/2.23	      6: evalDis1bb1in -> evalDis1bb3in : D'=1+D, [], cost: 1
4.79/2.23	
4.79/2.23	      7: evalDis1bb2in -> evalDis1bb3in : B'=1+B, [], cost: 1
4.79/2.23	
4.79/2.23	      8: evalDis1returnin -> evalDis1stop : [], cost: 1
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Removed unreachable and leaf rules:
4.79/2.23	
4.79/2.23	   Start location: evalDis1start
4.79/2.23	
4.79/2.23	      0: evalDis1start -> evalDis1entryin : [], cost: 1
4.79/2.23	
4.79/2.23	      1: evalDis1entryin -> evalDis1bb3in : A'=B, B'=A, C'=D, D'=C, [], cost: 1
4.79/2.23	
4.79/2.23	      2: evalDis1bb3in -> evalDis1bbin : [ A>=1+B ], cost: 1
4.79/2.23	
4.79/2.23	      4: evalDis1bbin -> evalDis1bb1in : [ C>=1+D ], cost: 1
4.79/2.23	
4.79/2.23	      5: evalDis1bbin -> evalDis1bb2in : [ D>=C ], cost: 1
4.79/2.23	
4.79/2.23	      6: evalDis1bb1in -> evalDis1bb3in : D'=1+D, [], cost: 1
4.79/2.23	
4.79/2.23	      7: evalDis1bb2in -> evalDis1bb3in : B'=1+B, [], cost: 1
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	### Simplification by acceleration and chaining ###
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Eliminated locations (on linear paths):
4.79/2.23	
4.79/2.23	   Start location: evalDis1start
4.79/2.23	
4.79/2.23	      9: evalDis1start -> evalDis1bb3in : A'=B, B'=A, C'=D, D'=C, [], cost: 2
4.79/2.23	
4.79/2.23	      2: evalDis1bb3in -> evalDis1bbin : [ A>=1+B ], cost: 1
4.79/2.23	
4.79/2.23	     10: evalDis1bbin -> evalDis1bb3in : D'=1+D, [ C>=1+D ], cost: 2
4.79/2.23	
4.79/2.23	     11: evalDis1bbin -> evalDis1bb3in : B'=1+B, [ D>=C ], cost: 2
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Eliminated locations (on tree-shaped paths):
4.79/2.23	
4.79/2.23	   Start location: evalDis1start
4.79/2.23	
4.79/2.23	      9: evalDis1start -> evalDis1bb3in : A'=B, B'=A, C'=D, D'=C, [], cost: 2
4.79/2.23	
4.79/2.23	     12: evalDis1bb3in -> evalDis1bb3in : D'=1+D, [ A>=1+B && C>=1+D ], cost: 3
4.79/2.23	
4.79/2.23	     13: evalDis1bb3in -> evalDis1bb3in : B'=1+B, [ A>=1+B && D>=C ], cost: 3
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Accelerating simple loops of location 2.
4.79/2.23	
4.79/2.23	   Accelerating the following rules:
4.79/2.23	
4.79/2.23	     12: evalDis1bb3in -> evalDis1bb3in : D'=1+D, [ A>=1+B && C>=1+D ], cost: 3
4.79/2.23	
4.79/2.23	     13: evalDis1bb3in -> evalDis1bb3in : B'=1+B, [ A>=1+B && D>=C ], cost: 3
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	   Accelerated rule 12 with metering function C-D, yielding the new rule 14.
4.79/2.23	
4.79/2.23	   Accelerated rule 13 with metering function A-B, yielding the new rule 15.
4.79/2.23	
4.79/2.23	   Removing the simple loops: 12 13.
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Accelerated all simple loops using metering functions (where possible):
4.79/2.23	
4.79/2.23	   Start location: evalDis1start
4.79/2.23	
4.79/2.23	      9: evalDis1start -> evalDis1bb3in : A'=B, B'=A, C'=D, D'=C, [], cost: 2
4.79/2.23	
4.79/2.23	     14: evalDis1bb3in -> evalDis1bb3in : D'=C, [ A>=1+B && C>=1+D ], cost: 3*C-3*D
4.79/2.23	
4.79/2.23	     15: evalDis1bb3in -> evalDis1bb3in : B'=A, [ A>=1+B && D>=C ], cost: 3*A-3*B
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Chained accelerated rules (with incoming rules):
4.79/2.23	
4.79/2.23	   Start location: evalDis1start
4.79/2.23	
4.79/2.23	      9: evalDis1start -> evalDis1bb3in : A'=B, B'=A, C'=D, D'=C, [], cost: 2
4.79/2.23	
4.79/2.23	     16: evalDis1start -> evalDis1bb3in : A'=B, B'=A, C'=D, [ B>=1+A && D>=1+C ], cost: 2-3*C+3*D
4.79/2.23	
4.79/2.23	     17: evalDis1start -> evalDis1bb3in : A'=B, C'=D, D'=C, [ B>=1+A && C>=D ], cost: 2-3*A+3*B
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Removed unreachable locations (and leaf rules with constant cost):
4.79/2.23	
4.79/2.23	   Start location: evalDis1start
4.79/2.23	
4.79/2.23	     16: evalDis1start -> evalDis1bb3in : A'=B, B'=A, C'=D, [ B>=1+A && D>=1+C ], cost: 2-3*C+3*D
4.79/2.23	
4.79/2.23	     17: evalDis1start -> evalDis1bb3in : A'=B, C'=D, D'=C, [ B>=1+A && C>=D ], cost: 2-3*A+3*B
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	### Computing asymptotic complexity ###
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Fully simplified ITS problem
4.79/2.23	
4.79/2.23	   Start location: evalDis1start
4.79/2.23	
4.79/2.23	     16: evalDis1start -> evalDis1bb3in : A'=B, B'=A, C'=D, [ B>=1+A && D>=1+C ], cost: 2-3*C+3*D
4.79/2.23	
4.79/2.23	     17: evalDis1start -> evalDis1bb3in : A'=B, C'=D, D'=C, [ B>=1+A && C>=D ], cost: 2-3*A+3*B
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Computing asymptotic complexity for rule 16
4.79/2.23	
4.79/2.23	   Solved the limit problem by the following transformations:
4.79/2.23	
4.79/2.23	      Created initial limit problem:
4.79/2.23	
4.79/2.23	      2-3*C+3*D (+), -A+B (+/+!), -C+D (+/+!) [not solved]
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	      removing all constraints (solved by SMT)
4.79/2.23	
4.79/2.23	      resulting limit problem: [solved]
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	      applying transformation rule (C) using substitution {C==0,D==n,A==-n,B==0}
4.79/2.23	
4.79/2.23	      resulting limit problem:
4.79/2.23	
4.79/2.23	      [solved]
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	   Solution:
4.79/2.23	
4.79/2.23	      C / 0
4.79/2.23	
4.79/2.23	      D / n
4.79/2.23	
4.79/2.23	      A / -n
4.79/2.23	
4.79/2.23	      B / 0
4.79/2.23	
4.79/2.23	   Resulting cost 2+3*n has complexity: Poly(n^1)
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Found new complexity Poly(n^1).
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	Obtained the following overall complexity (w.r.t. the length of the input n):
4.79/2.23	
4.79/2.23	   Complexity:  Poly(n^1)
4.79/2.23	
4.79/2.23	   Cpx degree:  1
4.79/2.23	
4.79/2.23	   Solved cost: 2+3*n
4.79/2.23	
4.79/2.23	   Rule cost:   2-3*C+3*D
4.79/2.23	
4.79/2.23	   Rule guard:  [ B>=1+A && D>=1+C ]
4.79/2.23	
4.79/2.23	
4.79/2.23	
4.79/2.23	WORST_CASE(Omega(n^1),?)
4.79/2.23	
4.79/2.23	
4.79/2.23	----------------------------------------
4.79/2.23	
4.79/2.23	(4)
4.79/2.23	BOUNDS(n^1, INF)
4.79/2.25	EOF