details

property	value
status	complete
benchmark	nesting-ex1.koat
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n104.star.cs.uiowa.edu
space	KoAT-2014

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	3.0137860775 seconds
cpu usage	6.699166861
max memory	3.63692032E8

stage attributes

key	value
output-size	20106
starexec-result	WORST_CASE(Omega(n^3), O(n^5))

output

/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^3), O(n^5)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^3, nat(Arg_1^2) + nat(max(Arg_1 * (nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))) + Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)), Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)) + Arg_1 * (-1 * min(-1 * Arg_1^2, 0) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))), 0) + nat(nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1)))) + max(2, 3 + 2 * Arg_1) + nat(2 * Arg_1)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 1010 ms] (2) BOUNDS(1, nat(Arg_1^2) + nat(max(Arg_1 * (nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))) + Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)), Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)) + Arg_1 * (-1 * min(-1 * Arg_1^2, 0) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))), 0) + nat(nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1)))) + max(2, 3 + 2 * Arg_1) + nat(2 * Arg_1)) (3) Loat Proof [FINISHED, 471 ms] (4) BOUNDS(n^3, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: l0(A, B, C, D) -> Com_1(l1(0, B, C, D)) :|: TRUE l1(A, B, C, D) -> Com_1(l2(A, B, 0, 0)) :|: B > 0 l2(A, B, C, D) -> Com_1(l2(A, B, C + 1, D + C)) :|: C < B l2(A, B, C, D) -> Com_1(l1(A + D, B - 1, C, D)) :|: C >= B l1(A, B, C, D) -> Com_1(l3(A, B, C, D)) :|: B <= 0 l3(A, B, C, D) -> Com_1(l3(A - 1, B, C, D)) :|: A > 0 The start-symbols are:[l0_4] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, max([0, max([0, max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, max([Arg_1*(min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])), min([-((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), -((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), Arg_1*(max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, Arg_1])+max([0, Arg_1])+max([2, 3+2*Arg_1])+max([0, Arg_1*Arg_1]) {O(n^5)}) Initial Complexity Problem: Start: l0 Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3 Temp_Vars: Locations: l0, l1, l2, l3 Transitions: l0(Arg_0,Arg_1,Arg_2,Arg_3) -> l1(0,Arg_1,Arg_2,Arg_3):|: l1(Arg_0,Arg_1,Arg_2,Arg_3) -> l2(Arg_0,Arg_1,0,0):|:0 <= Arg_0 && 1 <= Arg_1 l1(Arg_0,Arg_1,Arg_2,Arg_3) -> l3(Arg_0,Arg_1,Arg_2,Arg_3):|:0 <= Arg_0 && Arg_1 <= 0 l2(Arg_0,Arg_1,Arg_2,Arg_3) -> l1(Arg_0+Arg_3,Arg_1-1,Arg_2,Arg_3):|:0 <= Arg_3 && 0 <= Arg_2+Arg_3 && 1 <= Arg_1+Arg_3 && 0 <= Arg_0+Arg_3 && 0 <= Arg_2 && 1 <= Arg_1+Arg_2 && 0 <= Arg_0+Arg_2 && 1 <= Arg_1 && 1 <= Arg_0+Arg_1 && 0 <= Arg_0 && Arg_1 <= Arg_2 l2(Arg_0,Arg_1,Arg_2,Arg_3) -> l2(Arg_0,Arg_1,Arg_2+1,Arg_3+Arg_2):|:0 <= Arg_3 && 0 <= Arg_2+Arg_3 && 1 <= Arg_1+Arg_3 && 0 <= Arg_0+Arg_3 && 0 <= Arg_2 && 1 <= Arg_1+Arg_2 && 0 <= Arg_0+Arg_2 && 1 <= Arg_1 && 1 <= Arg_0+Arg_1 && 0 <= Arg_0 && Arg_2+1 <= Arg_1 l3(Arg_0,Arg_1,Arg_2,Arg_3) -> l3(Arg_0-1,Arg_1,Arg_2,Arg_3):|:Arg_1 <= 0 && Arg_1 <= Arg_0 && 0 <= Arg_0 && 1 <= Arg_0 Timebounds: Overall timebound: max([0, max([0, max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, max([Arg_1*(min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])), min([-((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), -((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), Arg_1*(max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, Arg_1])+max([0, Arg_1])+max([2, 3+2*Arg_1])+max([0, Arg_1*Arg_1]) {O(n^5)} 0: l0->l1: 1 {O(1)} 1: l1->l2: max([0, 1+2*Arg_1]) {O(n)} 4: l1->l3: 1 {O(1)} 2: l2->l2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)} 3: l2->l1: max([0, Arg_1]) {O(n)} 5: l3->l3: max([0, max([0, max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, max([Arg_1*(min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])), min([-((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), -((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), Arg_1*(max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])]) {O(n^5)} Costbounds: Overall costbound: max([0, max([0, max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, max([Arg_1*(min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])), min([-((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), -((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), Arg_1*(max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, Arg_1])+max([0, Arg_1])+max([2, 3+2*Arg_1])+max([0, Arg_1*Arg_1]) {O(n^5)} 0: l0->l1: 1 {O(1)} 1: l1->l2: max([0, 1+2*Arg_1]) {O(n)} 4: l1->l3: 1 {O(1)} 2: l2->l2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)} 3: l2->l1: max([0, Arg_1]) {O(n)} popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to Compl Integ Trans Syste 26843