details

property	value
status	complete
benchmark	nestedLoop.koat
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n071.star.cs.uiowa.edu
space	SAS10

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	4.10466 seconds
cpu usage	20.9235
user time	20.0459
system time	0.877611
max virtual memory	1.871556E7
max residence set size	280320.0

stage attributes

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

output

10.21/4.04 WORST_CASE(Omega(n^2), O(n^2)) 10.21/4.05 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 10.21/4.05 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.21/4.05 10.21/4.05 10.21/4.05 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, n^2). 10.21/4.05 10.21/4.05 (0) CpxIntTrs 10.21/4.05 (1) Koat Proof [FINISHED, 1182 ms] 10.21/4.05 (2) BOUNDS(1, n^2) 10.21/4.05 (3) Loat Proof [FINISHED, 2270 ms] 10.21/4.05 (4) BOUNDS(n^2, INF) 10.21/4.05 10.21/4.05 10.21/4.05 ---------------------------------------- 10.21/4.05 10.21/4.05 (0) 10.21/4.05 Obligation: 10.21/4.05 Complexity Int TRS consisting of the following rules: 10.21/4.05 start(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J, K, L)) :|: 0 >= A + 1 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= K && J <= K && L >= A && L <= A 10.21/4.05 start(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J, K, L)) :|: 0 >= E + 1 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= K && J <= K && L >= A && L <= A 10.21/4.05 start(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J, K, L)) :|: 0 >= C + 1 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= K && J <= K && L >= A && L <= A 10.21/4.05 start(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(stop(A, B, C, D, E, F, G, H, I, 0, K, L)) :|: A >= 0 && E >= 0 && B >= 0 && B <= 0 && C >= 0 && C <= 0 && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= K && J <= K && L >= A && L <= A 10.21/4.05 start(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl131(A, B, C, D, E, F, G, 0, I, 1, K, L)) :|: A >= 0 && C >= 1 && D >= 0 && D <= 0 && B >= C && B <= C && E >= 0 && E <= 0 && F >= G && F <= G && H >= I && H <= I && J >= K && J <= K && L >= A && L <= A 10.21/4.05 start(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl121(A, B, C, D, E, 0, G, 1, I, 0, K, L)) :|: E >= 1 && C >= 1 && L >= 0 && L <= 0 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= K && J <= K && A >= 0 && A <= 0 10.21/4.05 start(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl111(A, B, C, D, E, 1, G, 1, I, 0, K, L)) :|: A >= 1 && E >= 1 && C >= 1 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= K && J <= K && L >= A && L <= A 10.21/4.05 lbl131(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J, K, L)) :|: J >= C && E >= 0 && A >= 0 && C >= 1 && A + C >= J && J >= 1 && H >= E && H <= E && L >= A && L <= A && D >= E && D <= E && B >= C && B <= C 10.21/4.05 lbl131(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl131(A, B, C, D, E, F, G, 0, I, 1 + J, K, L)) :|: C >= J + 1 && A >= 0 && C >= 1 && A + C >= J && J >= 1 && H >= 0 && H <= 0 && D >= 0 && D <= 0 && L >= A && L <= A && E >= 0 && E <= 0 && B >= C && B <= C 10.21/4.05 lbl131(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl121(A, B, C, D, E, J, G, 1, I, J, K, L)) :|: E >= 1 && C >= J + 1 && J >= A && E >= 0 && A >= 0 && C >= 1 && A + C >= J && J >= 1 && H >= E && H <= E && L >= A && L <= A && D >= E && D <= E && B >= C && B <= C 10.21/4.05 lbl131(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl111(A, B, C, D, E, 1 + J, G, 1, I, J, K, L)) :|: A >= J + 1 && E >= 1 && C >= J + 1 && E >= 0 && A >= 0 && C >= 1 && A + C >= J && J >= 1 && H >= E && H <= E && L >= A && L <= A && D >= E && D <= E && B >= C && B <= C 10.21/4.05 lbl121(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl131(A, B, C, D, E, F, G, H, I, 1 + J, K, L)) :|: A + C >= F + 1 && A >= 0 && F >= A && E >= 1 && H >= E && H <= E && J >= F && J <= F && L >= A && L <= A && D >= E && D <= E && B >= C && B <= C 10.21/4.05 lbl121(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl121(A, B, C, D, E, J, G, 1 + H, I, J, K, L)) :|: E >= H + 1 && F >= A && A + C >= F + 1 && A >= 0 && E >= H && H >= 1 && J >= F && J <= F && L >= A && L <= A && D >= E && D <= E && B >= C && B <= C 10.21/4.05 lbl121(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl111(A, B, C, D, E, 1 + J, G, 1 + H, I, J, K, L)) :|: A >= F + 1 && E >= H + 1 && A + C >= F + 1 && A >= 0 && E >= H && F >= A && H >= 1 && J >= F && J <= F && L >= A && L <= A && D >= E && D <= E && B >= C && B <= C 10.21/4.05 lbl111(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl121(A, B, C, D, E, F, G, H, I, F, K, L)) :|: A >= J + 1 && E >= 1 && J >= 0 && C >= J + 1 && F >= A && F <= A && H >= 1 && H <= 1 && L >= A && L <= A && D >= E && D <= E && B >= C && B <= C 10.21/4.05 lbl111(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(lbl111(A, B, C, D, E, 1 + F, G, H, I, J, K, L)) :|: A >= F + 1 && F >= J + 1 && E >= 1 && J >= 0 && A >= F && C >= J + 1 && H >= 1 && H <= 1 && L >= A && L <= A && D >= E && D <= E && B >= C && B <= C 10.21/4.05 start0(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(start(A, C, C, E, E, G, G, I, I, K, K, A)) :|: TRUE 10.21/4.05 10.21/4.05 The start-symbols are:[start0_12] 10.21/4.05 10.21/4.05 10.21/4.05 ---------------------------------------- 10.21/4.05 10.21/4.05 (1) Koat Proof (FINISHED) 10.21/4.05 YES(?, 72*ar_2 + 66*ar_0 + 14*ar_4 + 12*ar_2*ar_4 + 11*ar_0*ar_4 + 84) 10.21/4.05 10.21/4.05 10.21/4.05 10.21/4.05 Initial complexity problem: 10.21/4.05 10.21/4.05 1: T: 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 0 >= ar_0 + 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_10 /\ ar_11 = ar_0 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 0 >= ar_4 + 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_10 /\ ar_11 = ar_0 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 0 >= ar_2 + 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_10 /\ ar_11 = ar_0 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, 0, ar_10, ar_11)) [ ar_0 >= 0 /\ ar_4 >= 0 /\ ar_1 = 0 /\ ar_2 = 0 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_10 /\ ar_11 = ar_0 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl131(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, 0, ar_8, 1, ar_10, ar_11)) [ ar_0 >= 0 /\ ar_2 >= 1 /\ ar_3 = 0 /\ ar_1 = ar_2 /\ ar_4 = 0 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_10 /\ ar_11 = ar_0 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, 0, ar_6, 1, ar_8, 0, ar_10, ar_11)) [ ar_4 >= 1 /\ ar_2 >= 1 /\ ar_11 = 0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_10 /\ ar_0 = 0 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, 1, ar_6, 1, ar_8, 0, ar_10, ar_11)) [ ar_0 >= 1 /\ ar_4 >= 1 /\ ar_2 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_10 /\ ar_11 = ar_0 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) lbl131(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ ar_9 >= ar_2 /\ ar_4 >= 0 /\ ar_0 >= 0 /\ ar_2 >= 1 /\ ar_0 + ar_2 >= ar_9 /\ ar_9 >= 1 /\ ar_7 = ar_4 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) lbl131(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl131(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, 0, ar_8, ar_9 + 1, ar_10, ar_11)) [ ar_2 >= ar_9 + 1 /\ ar_0 >= 0 /\ ar_2 >= 1 /\ ar_0 + ar_2 >= ar_9 /\ ar_9 >= 1 /\ ar_7 = 0 /\ ar_3 = 0 /\ ar_11 = ar_0 /\ ar_4 = 0 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) lbl131(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_9, ar_6, 1, ar_8, ar_9, ar_10, ar_11)) [ ar_4 >= 1 /\ ar_2 >= ar_9 + 1 /\ ar_9 >= ar_0 /\ ar_4 >= 0 /\ ar_0 >= 0 /\ ar_2 >= 1 /\ ar_0 + ar_2 >= ar_9 /\ ar_9 >= 1 /\ ar_7 = ar_4 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) lbl131(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_9 + 1, ar_6, 1, ar_8, ar_9, ar_10, ar_11)) [ ar_0 >= ar_9 + 1 /\ ar_4 >= 1 /\ ar_2 >= ar_9 + 1 /\ ar_4 >= 0 /\ ar_0 >= 0 /\ ar_2 >= 1 /\ ar_0 + ar_2 >= ar_9 /\ ar_9 >= 1 /\ ar_7 = ar_4 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl131(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9 + 1, ar_10, ar_11)) [ ar_0 + ar_2 >= ar_5 + 1 /\ ar_0 >= 0 /\ ar_5 >= ar_0 /\ ar_4 >= 1 /\ ar_7 = ar_4 /\ ar_9 = ar_5 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_9, ar_6, ar_7 + 1, ar_8, ar_9, ar_10, ar_11)) [ ar_4 >= ar_7 + 1 /\ ar_5 >= ar_0 /\ ar_0 + ar_2 >= ar_5 + 1 /\ ar_0 >= 0 /\ ar_4 >= ar_7 /\ ar_7 >= 1 /\ ar_9 = ar_5 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_9 + 1, ar_6, ar_7 + 1, ar_8, ar_9, ar_10, ar_11)) [ ar_0 >= ar_5 + 1 /\ ar_4 >= ar_7 + 1 /\ ar_0 + ar_2 >= ar_5 + 1 /\ ar_0 >= 0 /\ ar_4 >= ar_7 /\ ar_5 >= ar_0 /\ ar_7 >= 1 /\ ar_9 = ar_5 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_5, ar_10, ar_11)) [ ar_0 >= ar_9 + 1 /\ ar_4 >= 1 /\ ar_9 >= 0 /\ ar_2 >= ar_9 + 1 /\ ar_5 = ar_0 /\ ar_7 = 1 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ ar_0 >= ar_5 + 1 /\ ar_5 >= ar_9 + 1 /\ ar_4 >= 1 /\ ar_9 >= 0 /\ ar_0 >= ar_5 /\ ar_2 >= ar_9 + 1 /\ ar_7 = 1 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 (Comp: ?, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_6, ar_6, ar_8, ar_8, ar_10, ar_10, ar_0)) 10.21/4.05 10.21/4.05 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 0 <= 0 ] 10.21/4.05 10.21/4.05 start location: koat_start 10.21/4.05 10.21/4.05 leaf cost: 0 10.21/4.05 10.21/4.05 10.21/4.05 10.21/4.05 Testing for reachability in the complexity graph removes the following transitions from problem 1: 10.21/4.05 10.21/4.05 lbl131(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_9 + 1, ar_6, 1, ar_8, ar_9, ar_10, ar_11)) [ ar_0 >= ar_9 + 1 /\ ar_4 >= 1 /\ ar_2 >= ar_9 + 1 /\ ar_4 >= 0 /\ ar_0 >= 0 /\ ar_2 >= 1 /\ ar_0 + ar_2 >= ar_9 /\ ar_9 >= 1 /\ ar_7 = ar_4 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_9 + 1, ar_6, ar_7 + 1, ar_8, ar_9, ar_10, ar_11)) [ ar_0 >= ar_5 + 1 /\ ar_4 >= ar_7 + 1 /\ ar_0 + ar_2 >= ar_5 + 1 /\ ar_0 >= 0 /\ ar_4 >= ar_7 /\ ar_5 >= ar_0 /\ ar_7 >= 1 /\ ar_9 = ar_5 /\ ar_11 = ar_0 /\ ar_3 = ar_4 /\ ar_1 = ar_2 ] 10.21/4.05 10.21/4.05 We thus obtain the following problem: 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