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	n179.star.cs.uiowa.edu
space	SAS10

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	3.77826 seconds
cpu usage	8.64371
user time	8.17398
system time	0.469728
max virtual memory	1.8817244E7
max residence set size	276560.0

stage attributes

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

output

8.47/3.72 WORST_CASE(Omega(n^1), O(n^1)) 8.47/3.74 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 8.47/3.74 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.47/3.74 8.47/3.74 8.47/3.74 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). 8.47/3.74 8.47/3.74 (0) CpxIntTrs 8.47/3.74 (1) Koat Proof [FINISHED, 816 ms] 8.47/3.74 (2) BOUNDS(1, n^1) 8.47/3.74 (3) Loat Proof [FINISHED, 1857 ms] 8.47/3.74 (4) BOUNDS(n^1, INF) 8.47/3.74 8.47/3.74 8.47/3.74 ---------------------------------------- 8.47/3.74 8.47/3.74 (0) 8.47/3.74 Obligation: 8.47/3.74 Complexity Int TRS consisting of the following rules: 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 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 8.47/3.74 start0(A, B, C, D, E, F, G, H) -> Com_1(start(A, C, C, E, E, G, G, A)) :|: TRUE 8.47/3.74 8.47/3.74 The start-symbols are:[start0_8] 8.47/3.74 8.47/3.74 8.47/3.74 ---------------------------------------- 8.47/3.74 8.47/3.74 (1) Koat Proof (FINISHED) 8.47/3.74 YES(?, 44*ar_0 + 4335) 8.47/3.74 8.47/3.74 8.47/3.74 8.47/3.74 Initial complexity problem: 8.47/3.74 8.47/3.74 1: T: 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 (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)) 8.47/3.74 8.47/3.74 (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 ] 8.47/3.74 8.47/3.74 start location: koat_start 8.47/3.74 8.47/3.74 leaf cost: 0 8.47/3.74 8.47/3.74 8.47/3.74 8.47/3.74 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 Complexity_ITS 2019-03-21 04.46