3.60/1.82	WORST_CASE(?, O(1))
3.60/1.82	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
3.60/1.82	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.60/1.82	
3.60/1.82	
3.60/1.82	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, 1).
3.60/1.82	
3.60/1.82	(0) CpxIntTrs
3.60/1.82	(1) Koat Proof [FINISHED, 97 ms]
3.60/1.82	(2) BOUNDS(1, 1)
3.60/1.82	
3.60/1.82	
3.60/1.82	----------------------------------------
3.60/1.82	
3.60/1.82	(0)
3.60/1.82	Obligation:
3.60/1.82	Complexity Int TRS consisting of the following rules:
3.60/1.82	start(A, B, C, D) -> Com_1(lbl51(E, B, 0, D)) :|: A >= B && A <= B && C >= D && C <= D
3.60/1.82	lbl51(A, B, C, D) -> Com_1(stop(A, B, C, D)) :|: C >= A && C >= 0 && 9 >= C
3.60/1.82	lbl51(A, B, C, D) -> Com_1(stop(A, B, C, D)) :|: A >= C + 3 && C >= 0 && 9 >= C
3.60/1.82	lbl51(A, B, C, D) -> Com_1(cut(A, B, C, D)) :|: A >= C + 1 && C + 2 >= A && 9 >= A && C >= 0 && 9 >= C
3.60/1.82	lbl51(A, B, C, D) -> Com_1(stop(A, B, C, D)) :|: A >= 10 && A >= C + 1 && C + 2 >= A && C >= 0 && 9 >= C
3.60/1.82	cut(A, B, C, D) -> Com_1(lbl51(E, B, A, D)) :|: C + 2 >= A && 9 >= A && C >= 0 && A >= C + 1
3.60/1.82	start0(A, B, C, D) -> Com_1(start(B, B, D, D)) :|: TRUE
3.60/1.82	
3.60/1.82	The start-symbols are:[start0_4]
3.60/1.82	
3.60/1.82	
3.60/1.82	----------------------------------------
3.60/1.82	
3.60/1.82	(1) Koat Proof (FINISHED)
3.60/1.82	YES(?, 43)
3.60/1.82	
3.60/1.82	
3.60/1.82	
3.60/1.82	Initial complexity problem:
3.60/1.82	
3.60/1.82	1:	T:
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(lbl51(e, ar_1, 0, ar_3)) [ ar_0 = ar_1 /\ ar_2 = ar_3 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 3 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 10 /\ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3) -> Com_1(lbl51(e, ar_1, ar_0, ar_3)) [ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ ar_0 >= ar_2 + 1 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_1, ar_1, ar_3, ar_3))
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
3.60/1.82	
3.60/1.82		start location:	koat_start
3.60/1.82	
3.60/1.82		leaf cost:	0
3.60/1.82	
3.60/1.82	
3.60/1.82	
3.60/1.82	Repeatedly propagating knowledge in problem 1 produces the following problem:
3.60/1.82	
3.60/1.82	2:	T:
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(lbl51(e, ar_1, 0, ar_3)) [ ar_0 = ar_1 /\ ar_2 = ar_3 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 3 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 10 /\ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3) -> Com_1(lbl51(e, ar_1, ar_0, ar_3)) [ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ ar_0 >= ar_2 + 1 ]
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_1, ar_1, ar_3, ar_3))
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
3.60/1.82	
3.60/1.82		start location:	koat_start
3.60/1.82	
3.60/1.82		leaf cost:	0
3.60/1.82	
3.60/1.82	
3.60/1.82	
3.60/1.82	A polynomial rank function with
3.60/1.82	
3.60/1.82		Pol(start) = 1
3.60/1.82	
3.60/1.82		Pol(lbl51) = 1
3.60/1.82	
3.60/1.82		Pol(stop) = 0
3.60/1.82	
3.60/1.82		Pol(cut) = 1
3.60/1.82	
3.60/1.82		Pol(start0) = 1
3.60/1.82	
3.60/1.82		Pol(koat_start) = 1
3.60/1.82	
3.60/1.82	orients all transitions weakly and the transitions
3.60/1.82	
3.60/1.82		lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 10 /\ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82		lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82		lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 3 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82	strictly and produces the following problem:
3.60/1.82	
3.60/1.82	3:	T:
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(lbl51(e, ar_1, 0, ar_3)) [ ar_0 = ar_1 /\ ar_2 = ar_3 ]
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 3 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 10 /\ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3) -> Com_1(lbl51(e, ar_1, ar_0, ar_3)) [ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ ar_0 >= ar_2 + 1 ]
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_1, ar_1, ar_3, ar_3))
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
3.60/1.82	
3.60/1.82		start location:	koat_start
3.60/1.82	
3.60/1.82		leaf cost:	0
3.60/1.82	
3.60/1.82	
3.60/1.82	
3.60/1.82	A polynomial rank function with
3.60/1.82	
3.60/1.82		Pol(start) = 19
3.60/1.82	
3.60/1.82		Pol(lbl51) = -2*V_3 + 19
3.60/1.82	
3.60/1.82		Pol(stop) = 1
3.60/1.82	
3.60/1.82		Pol(cut) = -2*V_3 + 18
3.60/1.82	
3.60/1.82		Pol(start0) = 19
3.60/1.82	
3.60/1.82		Pol(koat_start) = 19
3.60/1.82	
3.60/1.82	orients all transitions weakly and the transitions
3.60/1.82	
3.60/1.82		lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.82	
3.60/1.82		cut(ar_0, ar_1, ar_2, ar_3) -> Com_1(lbl51(e, ar_1, ar_0, ar_3)) [ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ ar_0 >= ar_2 + 1 ]
3.60/1.82	
3.60/1.82	strictly and produces the following problem:
3.60/1.82	
3.60/1.82	4:	T:
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 1)     start(ar_0, ar_1, ar_2, ar_3) -> Com_1(lbl51(e, ar_1, 0, ar_3)) [ ar_0 = ar_1 /\ ar_2 = ar_3 ]
3.60/1.82	
3.60/1.82			(Comp: 1, Cost: 1)     lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.83	
3.60/1.83			(Comp: 1, Cost: 1)     lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 3 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.83	
3.60/1.83			(Comp: 19, Cost: 1)    lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.83	
3.60/1.83			(Comp: 1, Cost: 1)     lbl51(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 10 /\ ar_0 >= ar_2 + 1 /\ ar_2 + 2 >= ar_0 /\ ar_2 >= 0 /\ 9 >= ar_2 ]
3.60/1.83	
3.60/1.83			(Comp: 19, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3) -> Com_1(lbl51(e, ar_1, ar_0, ar_3)) [ ar_2 + 2 >= ar_0 /\ 9 >= ar_0 /\ ar_2 >= 0 /\ ar_0 >= ar_2 + 1 ]
3.60/1.83	
3.60/1.83			(Comp: 1, Cost: 1)     start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_1, ar_1, ar_3, ar_3))
3.60/1.83	
3.60/1.83			(Comp: 1, Cost: 0)     koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
3.60/1.83	
3.60/1.83		start location:	koat_start
3.60/1.83	
3.60/1.83		leaf cost:	0
3.60/1.83	
3.60/1.83	
3.60/1.83	
3.60/1.83	Complexity upper bound 43
3.60/1.83	
3.60/1.83	
3.60/1.83	
3.60/1.83	Time: 0.153 sec (SMT: 0.143 sec)
3.60/1.83	
3.60/1.83	
3.60/1.83	----------------------------------------
3.60/1.83	
3.60/1.83	(2)
3.60/1.83	BOUNDS(1, 1)
3.99/1.84	EOF