Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Compl Integ Trans Syste 26843 pair #381744128
details
property
value
status
complete
benchmark
realshellsort.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n081.star.cs.uiowa.edu
space
SAS10
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
15.9566049576 seconds
cpu usage
21.998461528
max memory
4.64642048E8
stage attributes
key
value
output-size
224398
starexec-result
WORST_CASE(?, O(n^3))
output
/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^3)) 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(1, n^3). (0) CpxIntTrs (1) Koat Proof [FINISHED, 1188 ms] (2) BOUNDS(1, n^3) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: start(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl21(A, B, C, D, E, F, G, H, I, J, K, L, M, N, Q, P)) :|: A >= B && A <= B && C >= D && C <= D && E >= F && E <= F && G >= H && G <= H && I >= J && I <= J && K >= L && K <= L && M >= N && M <= N && O >= P && O <= P lbl121(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl123(A, B, C, D, E, F, A, H, I, J, K, L, M, N, O, P)) :|: G >= 2 * A && 2 * A + 1 >= G && 2 * O + 1 >= L && O >= G && E >= 0 && G >= 1 && L >= 1 + E && K >= L && K <= L && I >= L && I <= L && M + 1 >= L && M + 1 <= L lbl123(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P)) :|: E >= 0 && 2 * O + 1 >= L && O >= 1 && L >= E + 1 && O >= 0 && G >= 0 && G <= 0 && K >= L && K <= L && I >= L && I <= L && M + 1 >= L && M + 1 <= L && A >= 0 && A <= 0 lbl123(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl121(Q, B, C, D, E, F, G, H, 0, J, K, L, M, N, O, P)) :|: A >= 1 && 0 >= L && A >= 0 && E >= 0 && 2 * O + 1 >= L && O >= 1 && L >= E + 1 && O >= 2 * A && K >= L && K <= L && I >= L && I <= L && M + 1 >= L && M + 1 <= L && G >= A && G <= A lbl123(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl71(A, B, Q, D, 0, F, G, H, 0, J, K, L, M, N, O, P)) :|: L >= 1 && A >= 1 && A >= 0 && E >= 0 && 2 * O + 1 >= L && O >= 1 && L >= E + 1 && O >= 2 * A && K >= L && K <= L && I >= L && I <= L && M + 1 >= L && M + 1 <= L && G >= A && G <= A lbl101(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl101(A, B, C, D, E - G, F, G, H, I, J, K, L, M, N, O, P)) :|: E >= G && I >= G + E && O >= G && L >= I + 1 && G >= 1 && 2 * O + 1 >= L && E >= 0 && K >= L && K <= L lbl101(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl53(A, B, C, D, E, F, G, H, 1 + I, J, K, L, I, N, O, P)) :|: I >= G + E && O >= G && L >= I + 1 && G >= 1 && 2 * O + 1 >= L && E >= 0 && K >= L && K <= L lbl71(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl101(A, B, C, D, E - G, F, G, H, I, J, K, L, M, N, O, P)) :|: E >= G && 2 * O + 1 >= L && O >= G && G >= 1 && E >= 0 && L >= E + 1 && I >= E && I <= E && K >= L && K <= L lbl71(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl53(A, B, C, D, E, F, G, H, 1 + I, J, K, L, I, N, O, P)) :|: 2 * O + 1 >= L && O >= G && G >= 1 && E >= 0 && L >= E + 1 && I >= E && I <= E && K >= L && K <= L lbl53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl121(Q, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P)) :|: L >= 1 + E && G >= 1 && E >= 0 && O >= G && 2 * O + 1 >= L && I >= L && I <= L && K >= L && K <= L && M + 1 >= L && M + 1 <= L lbl53(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl71(A, B, Q, D, I, F, G, H, I, J, K, L, M, N, O, P)) :|: L >= M + 2 && L >= M + 1 && M >= E && G >= 1 && E >= 0 && O >= G && 2 * O + 1 >= L && I >= M + 1 && I <= M + 1 && K >= L && K <= L lbl21(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(stop(A, B, C, D, E, F, O, H, I, J, K, L, M, N, O, P)) :|: L >= 2 * O && 0 >= O && 2 * O + 1 >= L && M >= N && M <= N && A >= B && A <= B && C >= D && C <= D && E >= F && E <= F && G >= H && G <= H && I >= J && I <= J && K >= L && K <= L lbl21(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(lbl71(A, B, Q, D, 0, F, O, H, 0, J, K, L, M, N, O, P)) :|: L >= 2 * O && O >= 1 && 2 * O + 1 >= L && M >= N && M <= N && A >= B && A <= B && C >= D && C <= D && E >= F && E <= F && G >= H && G <= H && I >= J && I <= J && K >= L && K <= L start0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P) -> Com_1(start(B, B, D, D, F, F, H, H, J, J, L, L, N, N, P, P)) :|: TRUE The start-symbols are:[start0_16] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 120*ar_11 + 66*ar_11^2 + 9*ar_11^3 + 50) 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, ar_12, ar_13, ar_14, ar_15) -> Com_1(lbl21(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_12, ar_13, q, ar_15)) [ 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_12 = ar_13 /\ ar_14 = ar_15 ] (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, ar_12, ar_13, ar_14, ar_15) -> Com_1(lbl123(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_0, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_6 >= 2*ar_0 /\ 2*ar_0 + 1 >= ar_6 /\ 2*ar_14 + 1 >= ar_11 /\ ar_14 >= ar_6 /\ ar_4 >= 0 /\ ar_6 >= 1 /\ ar_11 >= ar_4 + 1 /\ ar_10 = ar_11 /\ ar_8 = ar_11 /\ ar_12 + 1 = ar_11 ] (Comp: ?, Cost: 1) lbl123(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_12, ar_13, ar_14, ar_15) -> 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_12, ar_13, ar_14, ar_15)) [ ar_4 >= 0 /\ 2*ar_14 + 1 >= ar_11 /\ ar_14 >= 1 /\ ar_11 >= ar_4 + 1 /\ ar_14 >= 0 /\ ar_6 = 0 /\ ar_10 = ar_11 /\ ar_8 = ar_11 /\ ar_12 + 1 = ar_11 /\ ar_0 = 0 ] (Comp: ?, Cost: 1) lbl123(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl121(q, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, 0, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_0 >= 1 /\ 0 >= ar_11 /\ ar_0 >= 0 /\ ar_4 >= 0 /\ 2*ar_14 + 1 >= ar_11 /\ ar_14 >= 1 /\ ar_11 >= ar_4 + 1 /\ ar_14 >= 2*ar_0 /\ ar_10 = ar_11 /\ ar_8 = ar_11 /\ ar_12 + 1 = ar_11 /\ ar_6 = ar_0 ] (Comp: ?, Cost: 1) lbl123(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl71(ar_0, ar_1, q, ar_3, 0, ar_5, ar_6, ar_7, 0, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_11 >= 1 /\ ar_0 >= 1 /\ ar_0 >= 0 /\ ar_4 >= 0 /\ 2*ar_14 + 1 >= ar_11 /\ ar_14 >= 1 /\ ar_11 >= ar_4 + 1 /\ ar_14 >= 2*ar_0 /\ ar_10 = ar_11 /\ ar_8 = ar_11 /\ ar_12 + 1 = ar_11 /\ ar_6 = ar_0 ] (Comp: ?, Cost: 1) lbl101(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl101(ar_0, ar_1, ar_2, ar_3, ar_4 - ar_6, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_4 >= ar_6 /\ ar_8 >= ar_6 + ar_4 /\ ar_14 >= ar_6 /\ ar_11 >= ar_8 + 1 /\ ar_6 >= 1 /\ 2*ar_14 + 1 >= ar_11 /\ ar_4 >= 0 /\ ar_10 = ar_11 ] (Comp: ?, Cost: 1) lbl101(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl53(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8 + 1, ar_9, ar_10, ar_11, ar_8, ar_13, ar_14, ar_15)) [ ar_8 >= ar_6 + ar_4 /\ ar_14 >= ar_6 /\ ar_11 >= ar_8 + 1 /\ ar_6 >= 1 /\ 2*ar_14 + 1 >= ar_11 /\ ar_4 >= 0 /\ ar_10 = ar_11 ] (Comp: ?, Cost: 1) lbl71(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl101(ar_0, ar_1, ar_2, ar_3, ar_4 - ar_6, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_4 >= ar_6 /\ 2*ar_14 + 1 >= ar_11 /\ ar_14 >= ar_6 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_11 >= ar_4 + 1 /\ ar_8 = ar_4 /\ ar_10 = ar_11 ] (Comp: ?, Cost: 1) lbl71(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl53(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8 + 1, ar_9, ar_10, ar_11, ar_8, ar_13, ar_14, ar_15)) [ 2*ar_14 + 1 >= ar_11 /\ ar_14 >= ar_6 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_11 >= ar_4 + 1 /\ ar_8 = ar_4 /\ ar_10 = ar_11 ] (Comp: ?, Cost: 1) lbl53(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl121(q, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_11 >= ar_4 + 1 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_14 >= ar_6 /\ 2*ar_14 + 1 >= ar_11 /\ ar_8 = ar_11 /\ ar_10 = ar_11 /\ ar_12 + 1 = ar_11 ] (Comp: ?, Cost: 1) lbl53(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl71(ar_0, ar_1, q, ar_3, ar_8, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_11 >= ar_12 + 2 /\ ar_11 >= ar_12 + 1 /\ ar_12 >= ar_4 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_14 >= ar_6 /\ 2*ar_14 + 1 >= ar_11 /\ ar_8 = ar_12 + 1 /\ ar_10 = ar_11 ] (Comp: ?, Cost: 1) lbl21(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_12, ar_13, ar_14, ar_15) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_14, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_11 >= 2*ar_14 /\ 0 >= ar_14 /\ 2*ar_14 + 1 >= ar_11 /\ ar_12 = ar_13 /\ ar_0 = ar_1 /\ ar_2 = ar_3 /\ ar_4 = ar_5 /\ ar_6 = ar_7 /\ ar_8 = ar_9 /\ ar_10 = ar_11 ] (Comp: ?, Cost: 1) lbl21(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl71(ar_0, ar_1, q, ar_3, 0, ar_5, ar_14, ar_7, 0, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_11 >= 2*ar_14 /\ ar_14 >= 1 /\ 2*ar_14 + 1 >= ar_11 /\ ar_12 = ar_13 /\ ar_0 = ar_1 /\ ar_2 = ar_3 /\ ar_4 = ar_5 /\ ar_6 = ar_7 /\ ar_8 = ar_9 /\ ar_10 = ar_11 ] (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, ar_12, ar_13, ar_14, ar_15) -> Com_1(start(ar_1, ar_1, ar_3, ar_3, ar_5, ar_5, ar_7, ar_7, ar_9, ar_9, ar_11, ar_11, ar_13, ar_13, ar_15, ar_15)) (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, ar_12, ar_13, ar_14, ar_15) -> 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, ar_12, ar_13, ar_14, ar_15)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Testing for reachability in the complexity graph removes the following transition from problem 1: lbl123(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl121(q, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, 0, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_0 >= 1 /\ 0 >= ar_11 /\ ar_0 >= 0 /\ ar_4 >= 0 /\ 2*ar_14 + 1 >= ar_11 /\ ar_14 >= 1 /\ ar_11 >= ar_4 + 1 /\ ar_14 >= 2*ar_0 /\ ar_10 = ar_11 /\ ar_8 = ar_11 /\ ar_12 + 1 = ar_11 /\ ar_6 = ar_0 ] We thus obtain the following problem: 2: T: (Comp: ?, Cost: 1) lbl101(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl53(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8 + 1, ar_9, ar_10, ar_11, ar_8, ar_13, ar_14, ar_15)) [ ar_8 >= ar_6 + ar_4 /\ ar_14 >= ar_6 /\ ar_11 >= ar_8 + 1 /\ ar_6 >= 1 /\ 2*ar_14 + 1 >= ar_11 /\ ar_4 >= 0 /\ ar_10 = ar_11 ] (Comp: ?, Cost: 1) lbl101(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_12, ar_13, ar_14, ar_15) -> Com_1(lbl101(ar_0, ar_1, ar_2, ar_3, ar_4 - ar_6, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12, ar_13, ar_14, ar_15)) [ ar_4 >= ar_6 /\ ar_8 >= ar_6 + ar_4 /\ ar_14 >= ar_6 /\ ar_11 >= ar_8 + 1 /\ ar_6 >= 1 /\ 2*ar_14 + 1 >= ar_11 /\ ar_4 >= 0 /\ ar_10 = ar_11 ]
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Compl Integ Trans Syste 26843