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	n094.star.cs.uiowa.edu
space	KoAT-2014

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	3.51918 seconds
cpu usage	6.94833
user time	6.57669
system time	0.371635
max virtual memory	1.8640404E7
max residence set size	225064.0

stage attributes

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

output

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

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

job log

popout

actions

all output return to Complexity_ITS 2019-03-21 04.46