Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Compl Integ Trans Syste 26843 pair #381744293
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
n086.star.cs.uiowa.edu
space
SAS10
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
3.96835207939 seconds
cpu usage
10.391855081
max memory
4.87972864E8
stage attributes
key
value
output-size
191581
starexec-result
WORST_CASE(Omega(n^2), O(n^2))
output
/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), O(n^2)) proof of /export/starexec/sandbox/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^2, n^2). (0) CpxIntTrs (1) Koat Proof [FINISHED, 1129 ms] (2) BOUNDS(1, n^2) (3) Loat Proof [FINISHED, 2298 ms] (4) BOUNDS(n^2, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 The start-symbols are:[start0_12] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 72*ar_2 + 66*ar_0 + 14*ar_4 + 12*ar_2*ar_4 + 11*ar_0*ar_4 + 84) Initial complexity problem: 1: T: (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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)) (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 ] start location: koat_start leaf cost: 0 Testing for reachability in the complexity graph removes the following transitions from problem 1:
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Compl Integ Trans Syste 26843