Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Compl Integ Trans Syste 26843 pair #381744506
details
property
value
status
complete
benchmark
random2d.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n056.star.cs.uiowa.edu
space
SAS10
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
8.42494702339 seconds
cpu usage
19.476768598
max memory
5.0817024E8
stage attributes
key
value
output-size
56070
starexec-result
WORST_CASE(Omega(n^1), O(n^1))
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^1), O(n^1)) 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^1, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 1048 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 6653 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: start(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, 0, C, 0, E, F, G, 0, I, J)) :|: 0 >= A && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= A && J <= A start(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, 0, C, 0, E, K, G, 1, I, J)) :|: A >= 1 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= A && J <= A lbl21(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 1 && A + D >= B + 1 && A + B >= D + 1 && A >= D + B + 1 && H >= A && H <= A && J >= A && J <= A lbl21(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 1 && H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && J >= A && J <= A lbl121(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 2 && A + D >= B + 2 && A + B >= D && A >= D + B && H >= A && H <= A && F >= 0 && F <= 0 && J >= A && J <= A lbl121(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 2 && H + D >= B + 2 && H + B >= D && H >= D + B && F >= 0 && F <= 0 && J >= A && J <= A lbl141(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 0 && A + D >= B && A + B >= D + 2 && A >= D + B + 2 && H >= A && H <= A && F >= 1 && F <= 1 && J >= A && J <= A lbl141(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 0 && H + D >= B && H + B >= D + 2 && H >= D + B + 2 && F >= 1 && F <= 1 && J >= A && J <= A lbl171(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 2 && A + D >= B && A + B >= D + 2 && A >= D + B && H >= A && H <= A && F >= 2 && F <= 2 && J >= A && J <= A lbl171(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 2 && H + D >= B && H + B >= D + 2 && H >= D + B && F >= 2 && F <= 2 && J >= A && J <= A lbl191(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 0 && A + D >= B + 2 && A + B >= D && A >= D + B + 2 && H >= A && H <= A && F >= 3 && F <= 3 && J >= A && J <= A lbl191(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 0 && H + D >= B + 2 && H + B >= D && H >= D + B + 2 && F >= 3 && F <= 3 && J >= A && J <= A lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl21(A, B, C, D, E, F, G, H, I, J)) :|: 0 >= F + 1 && H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && J >= A && J <= A lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl21(A, B, C, D, E, F, G, H, I, J)) :|: F >= 4 && H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && J >= A && J <= A lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl121(A, B, C, 1 + D, E, F, G, H, I, J)) :|: H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && F >= 0 && F <= 0 && J >= A && J <= A lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl141(A, B, C, D - 1, E, F, G, H, I, J)) :|: H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && F >= 1 && F <= 1 && J >= A && J <= A lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl171(A, 1 + B, C, D, E, F, G, H, I, J)) :|: H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && F >= 2 && F <= 2 && J >= A && J <= A lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl191(A, B - 1, C, D, E, F, G, H, I, J)) :|: H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && F >= 3 && F <= 3 && J >= A && J <= A start0(A, B, C, D, E, F, G, H, I, J) -> Com_1(start(A, C, C, E, E, G, G, I, I, A)) :|: TRUE The start-symbols are:[start0_10] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 44*ar_0 + 8) 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) -> Com_1(stop(ar_0, 0, ar_2, 0, ar_4, ar_5, ar_6, 0, ar_8, ar_9)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = 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) -> Com_1(lbl81(ar_0, 0, ar_2, 0, ar_4, k, ar_6, 1, ar_8, ar_9)) [ ar_0 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 1 /\ ar_0 + ar_3 >= ar_1 + 1 /\ ar_0 + ar_1 >= ar_3 + 1 /\ ar_0 >= ar_3 + ar_1 + 1 /\ ar_7 = ar_0 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 0 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 0 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 1 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 1 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 2 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 2 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 3 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 3 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 >= ar_5 + 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_5 >= 4 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3 + 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 0 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl141(ar_0, ar_1, ar_2, ar_3 - 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 1 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl171(ar_0, ar_1 + 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 2 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl191(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 3 /\ ar_9 = ar_0 ] (Comp: ?, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_6, ar_6, ar_8, ar_8, 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) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 <= 0 ] start location: koat_start
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Compl Integ Trans Syste 26843