details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	3.63659000397 seconds
cpu usage	8.515758735
max memory	5.15219456E8

stage attributes

key	value
output-size	47668
starexec-result	WORST_CASE(Omega(n^1), O(n^1))

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^1), O(n^1)) 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^1, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 788 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 1783 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) -> Com_1(stop(A, H - 10, C, 1, E, H, G, H)) :|: A >= 101 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= A && H <= A start(A, B, C, D, E, F, G, H) -> Com_1(lbl111(A, B, C, 2, E, 11 + H, G, H)) :|: 100 >= A && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= A && H <= A lbl161(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: 89 >= A && D >= 1 && D <= 1 && H >= A && H <= A && F >= 101 && F <= 101 && B >= 91 && B <= 91 lbl161(A, B, C, D, E, F, G, H) -> Com_1(lbl161(A, F - 20, C, D - 1, E, F - 10, G, H)) :|: 0 >= 10 && 89 >= A && 0 >= 1 && D >= 2 && D <= 2 && H >= A && H <= A && F >= 101 && F <= 101 && B >= 91 && B <= 91 lbl161(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: 0 >= 2 && 89 >= A && H >= A && H <= A && F >= 101 && F <= 101 && D >= 1 && D <= 1 && B >= 91 && B <= 91 lbl161(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: 0 >= 1 && 89 >= A && H >= A && H <= A && F >= 101 && F <= 101 && D >= 1 && D <= 1 && B >= 91 && B <= 91 lbl161(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D - 1, E, F - 9, G, H)) :|: 0 >= 10 && 0 >= 2 && 89 >= A && H >= A && H <= A && F >= 101 && F <= 101 && D >= 1 && D <= 1 && B >= 91 && B <= 91 lbl221(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: 1 >= D && D >= 2 && F >= 102 && 111 >= F && F + 10 >= A + 11 * D && 89 >= A && H >= A && H <= A && B >= C && B <= C lbl221(A, B, C, D, E, F, G, H) -> Com_1(lbl161(A, F - 20, C, D - 1, E, F - 10, G, H)) :|: 99 >= A && 89 >= A && F >= 111 && F <= 111 && D >= 2 && D <= 2 && H >= A && H <= A && B >= C && B <= C lbl221(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && F + 10 >= A + 11 * D && 89 >= A && H >= A && H <= A && B >= C && B <= C lbl221(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: D >= 2 && 110 >= F && F >= 102 && 111 >= F && F + 10 >= A + 11 * D && 89 >= A && H >= A && H <= A && B >= C && B <= C lbl221(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D - 1, E, F - 9, G, H)) :|: D >= 3 && D >= 2 && 121 >= A + 11 * D && 89 >= A && F >= 111 && F <= 111 && H >= A && H <= A && B >= C && B <= C lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl111(A, B, C, 1 + D, E, 11 + F, G, H)) :|: 111 >= 11 * D + A && 122 >= 11 * D + A && 11 * D >= 22 && H >= A && H <= A && B >= C && B <= C && F + 11 >= 11 * D + A && F + 11 <= 11 * D + A lbl111(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: 11 * D + A >= 112 && 1 >= D && 122 >= 11 * D + A && 11 * D >= 22 && H >= A && H <= A && B >= C && B <= C && F + 11 >= 11 * D + A && F + 11 <= 11 * D + A lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl161(A, F - 20, C, D - 1, E, F - 10, G, H)) :|: F >= 111 && F <= 111 && D >= 2 && D <= 2 && H >= 100 && H <= 100 && B >= C && B <= C && A >= 100 && A <= 100 lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: 11 * D + A >= 112 && D >= 3 && 121 >= 11 * D + A && 122 >= 11 * D + A && 11 * D >= 22 && H >= A && H <= A && B >= C && B <= C && F + 11 >= 11 * D + A && F + 11 <= 11 * D + A lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: 11 * D + A >= 112 && D >= 2 && 121 >= 11 * D + A && 122 >= 11 * D + A && 11 * D >= 22 && H >= A && H <= A && B >= C && B <= C && F + 11 >= 11 * D + A && F + 11 <= 11 * D + A lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D - 1, E, F - 9, G, H)) :|: D >= 3 && 11 * D >= 22 && F >= 111 && F <= 111 && H + 11 * D >= 122 && H + 11 * D <= 122 && B >= C && B <= C && A + 11 * D >= 122 && A + 11 * D <= 122 start0(A, B, C, D, E, F, G, H) -> Com_1(start(A, C, C, E, E, G, G, A)) :|: TRUE The start-symbols are:[start0_8] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 44*ar_0 + 4335) 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) -> Com_1(stop(ar_0, ar_7 - 10, ar_2, 1, ar_4, ar_7, ar_6, ar_7)) [ ar_0 >= 101 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_0 ] (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl111(ar_0, ar_1, ar_2, 2, ar_4, ar_7 + 11, ar_6, ar_7)) [ 100 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_0 ] (Comp: ?, Cost: 1) lbl161(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7)) [ 89 >= ar_0 /\ ar_3 = 1 /\ ar_7 = ar_0 /\ ar_5 = 101 /\ ar_1 = 91 ] (Comp: ?, Cost: 1) lbl161(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl161(ar_0, ar_5 - 20, ar_2, ar_3 - 1, ar_4, ar_5 - 10, ar_6, ar_7)) [ 0 >= 10 /\ 89 >= ar_0 /\ 0 >= 1 /\ ar_3 = 2 /\ ar_7 = ar_0 /\ ar_5 = 101 /\ ar_1 = 91 ] (Comp: ?, Cost: 1) lbl161(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7)) [ 0 >= 2 /\ 89 >= ar_0 /\ ar_7 = ar_0 /\ ar_5 = 101 /\ ar_3 = 1 /\ ar_1 = 91 ] (Comp: ?, Cost: 1) lbl161(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7)) [ 0 >= 1 /\ 89 >= ar_0 /\ ar_7 = ar_0 /\ ar_5 = 101 /\ ar_3 = 1 /\ ar_1 = 91 ] (Comp: ?, Cost: 1) lbl161(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl221(ar_0, ar_1, ar_2, ar_3 - 1, ar_4, ar_5 - 9, ar_6, ar_7)) [ 0 >= 10 /\ 0 >= 2 /\ 89 >= ar_0 /\ ar_7 = ar_0 /\ ar_5 = 101 /\ ar_3 = 1 /\ ar_1 = 91 ] (Comp: ?, Cost: 1) lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7)) [ 1 >= ar_3 /\ ar_3 >= 2 /\ ar_5 >= 102 /\ 111 >= ar_5 /\ ar_5 + 10 >= ar_0 + 11*ar_3 /\ 89 >= ar_0 /\ ar_7 = ar_0 /\ ar_1 = ar_2 ] (Comp: ?, Cost: 1) lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl161(ar_0, ar_5 - 20, ar_2, ar_3 - 1, ar_4, ar_5 - 10, ar_6, ar_7)) [ 99 >= ar_0 /\ 89 >= ar_0 /\ ar_5 = 111 /\ ar_3 = 2 /\ ar_7 = ar_0 /\ ar_1 = ar_2 ] (Comp: ?, Cost: 1) lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7)) [ ar_3 >= 3 /\ 110 >= ar_5 /\ ar_3 >= 2 /\ ar_5 >= 102 /\ 111 >= ar_5 /\ ar_5 + 10 >= ar_0 + 11*ar_3 /\ 89 >= ar_0 /\ ar_7 = ar_0 /\ ar_1 = ar_2 ] (Comp: ?, Cost: 1) lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7)) [ ar_3 >= 2 /\ 110 >= ar_5 /\ ar_5 >= 102 /\ 111 >= ar_5 /\ ar_5 + 10 >= ar_0 + 11*ar_3 /\ 89 >= ar_0 /\ ar_7 = ar_0 /\ ar_1 = ar_2 ] (Comp: ?, Cost: 1) lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl221(ar_0, ar_1, ar_2, ar_3 - 1, ar_4, ar_5 - 9, ar_6, ar_7)) [ ar_3 >= 3 /\ ar_3 >= 2 /\ 121 >= ar_0 + 11*ar_3 /\ 89 >= ar_0 /\ ar_5 = 111 /\ ar_7 = ar_0 /\ ar_1 = ar_2 ] (Comp: ?, Cost: 1) lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl111(ar_0, ar_1, ar_2, ar_3 + 1, ar_4, ar_5 + 11, ar_6, ar_7)) [ 111 >= 11*ar_3 + ar_0 /\ 122 >= 11*ar_3 + ar_0 /\ 11*ar_3 >= 22 /\ ar_7 = ar_0 /\ ar_1 = ar_2 /\ ar_5 + 11 = 11*ar_3 + ar_0 ] (Comp: ?, Cost: 1) lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7)) [ 11*ar_3 + ar_0 >= 112 /\ 1 >= ar_3 /\ 122 >= 11*ar_3 + ar_0 /\ 11*ar_3 >= 22 /\ ar_7 = ar_0 /\ ar_1 = ar_2 /\ ar_5 + 11 = 11*ar_3 + ar_0 ] (Comp: ?, Cost: 1) lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl161(ar_0, ar_5 - 20, ar_2, ar_3 - 1, ar_4, ar_5 - 10, ar_6, ar_7)) [ ar_5 = 111 /\ ar_3 = 2 /\ ar_7 = 100 /\ ar_1 = ar_2 /\ ar_0 = 100 ] (Comp: ?, Cost: 1) lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7)) [ 11*ar_3 + ar_0 >= 112 /\ ar_3 >= 3 /\ 121 >= 11*ar_3 + ar_0 /\ 122 >= 11*ar_3 + ar_0 /\ 11*ar_3 >= 22 /\ ar_7 = ar_0 /\ ar_1 = ar_2 /\ ar_5 + 11 = 11*ar_3 + ar_0 ] (Comp: ?, Cost: 1) lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl221(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7)) [ 11*ar_3 + ar_0 >= 112 /\ ar_3 >= 2 /\ 121 >= 11*ar_3 + ar_0 /\ 122 >= 11*ar_3 + ar_0 /\ 11*ar_3 >= 22 /\ ar_7 = ar_0 /\ ar_1 = ar_2 /\ ar_5 + 11 = 11*ar_3 + ar_0 ] (Comp: ?, Cost: 1) lbl111(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(lbl221(ar_0, ar_1, ar_2, ar_3 - 1, ar_4, ar_5 - 9, ar_6, ar_7)) [ ar_3 >= 3 /\ 11*ar_3 >= 22 /\ ar_5 = 111 /\ ar_7 + 11*ar_3 = 122 /\ ar_1 = ar_2 /\ ar_0 + 11*ar_3 = 122 ] (Comp: ?, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_6, ar_6, ar_0)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7)) [ 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