details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	2.98515 seconds
cpu usage	7.83301
user time	7.39243
system time	0.440583
max virtual memory	1.884882E7
max residence set size	246088.0

stage attributes

key	value
starexec-result	WORST_CASE(?, O(1))

output

7.70/2.92 WORST_CASE(?, O(1)) 7.70/2.93 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 7.70/2.93 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.70/2.93 7.70/2.93 7.70/2.93 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, 1). 7.70/2.93 7.70/2.93 (0) CpxIntTrs 7.70/2.93 (1) Koat Proof [FINISHED, 1211 ms] 7.70/2.93 (2) BOUNDS(1, 1) 7.70/2.93 7.70/2.93 7.70/2.93 ---------------------------------------- 7.70/2.93 7.70/2.93 (0) 7.70/2.93 Obligation: 7.70/2.93 Complexity Int TRS consisting of the following rules: 7.70/2.93 f0(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f15(50, 5, 0, D, E, F, G, H, I, J, K, L, M)) :|: TRUE 7.70/2.93 f15(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f19(A, B, C, 0, 0, F, G, H, I, J, K, L, M)) :|: B >= C 7.70/2.93 f19(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f19(A, B, C, D + N, E + 1, F, G, H, I, J, K, L, M)) :|: B >= E && E >= C + 1 7.70/2.93 f19(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f19(A, B, C, D + N, E + 1, F, G, H, I, J, K, L, M)) :|: C >= 1 + E && B >= E 7.70/2.93 f19(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f19(A, B, C, D + N, C + 1, F, G, H, I, J, K, L, M)) :|: B >= E && C >= E && C <= E 7.70/2.93 f33(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f36(A, B, C, D, E, F, G, G + 1, I, J, K, L, M)) :|: F >= G + 1 7.70/2.93 f36(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f41(A, B, C, D, E, F, G, H, N, 0, K, L, M)) :|: 0 >= G + 1 && F >= H 7.70/2.93 f36(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f41(A, B, C, D, E, F, G, H, N, 0, K, L, M)) :|: G >= 1 && F >= H 7.70/2.93 f41(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f41(A, B, C, D, E, F, G, H, N, J + 1, K, L, M)) :|: G >= J + 1 7.70/2.93 f36(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f36(A, B, C, D, E, F, 0, H + 1, N, J, K, L, M)) :|: F >= H && G >= 0 && G <= 0 7.70/2.93 f50(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f54(A, B, C, D, E, F, G, H, N, 0, K, L, M)) :|: F >= H 7.70/2.93 f54(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f54(A, B, C, D, E, F, G, H, N, J + 1, K, L, M)) :|: G >= J 7.70/2.93 f66(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f70(A, B, C, D, E, F, G, 0, N, J, K, L, M)) :|: F >= G 7.70/2.93 f70(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f70(A, B, C, D, E, F, G, H + 1, N, J, K, L, M)) :|: G >= H + 1 7.70/2.93 f80(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f84(A, B, C, D, E, F, G, G + 1, N, J, K, L, M)) :|: G >= 0 7.70/2.93 f84(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f84(A, B, C, D, E, F, G, H + 1, N, J, K, L, M)) :|: F >= H 7.70/2.93 f84(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f80(A, B, C, D, E, F, G - 1, H, I, J, K, L, M)) :|: H >= 1 + F 7.70/2.93 f80(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f96(A, B, C, D, E, F, G, H, I, J, 0, 0, M)) :|: 0 >= G + 1 7.70/2.93 f70(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f66(A, B, C, D, E, F, G + 1, H, I, J, K, L, M)) :|: H >= G 7.70/2.93 f66(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f80(A, B, C, D, E, F, F - 1, H, I, J, K, L, M)) :|: G >= 1 + F 7.70/2.93 f54(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f50(A, B, C, D, E, F, G, H + 1, I, J, K, L, M)) :|: J >= 1 + G 7.70/2.93 f50(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f33(A, B, C, D, E, F, G + 1, H, I, J, K, L, M)) :|: H >= 1 + F 7.70/2.93 f41(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f36(A, B, C, D, E, F, G, H + 1, I, J, K, L, M)) :|: J >= G 7.70/2.93 f36(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f50(A, B, C, D, E, F, G, G + 1, I, J, K, L, M)) :|: H >= 1 + F 7.70/2.93 f33(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f66(A, B, C, D, E, F, 1, H, I, J, K, L, M)) :|: G >= F 7.70/2.93 f19(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f15(A, B, C + 1, D, E, F, G, H, I, J, K, L, M)) :|: E >= 1 + B 7.70/2.93 f15(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f33(A, B, C, D, E, B, 0, H, I, J, K, L, A)) :|: C >= 1 + B 7.70/2.93 7.70/2.93 The start-symbols are:[f0_13] 7.70/2.93 7.70/2.93 7.70/2.93 ---------------------------------------- 7.70/2.93 7.70/2.93 (1) Koat Proof (FINISHED) 7.70/2.93 YES(?, 1505869237) 7.70/2.93 7.70/2.93 7.70/2.93 7.70/2.93 Initial complexity problem: 7.70/2.93 7.70/2.93 1: T: 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f0(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) -> Com_1(f15(50, 5, 0, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12)) 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f15(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) -> Com_1(f19(ar_0, ar_1, ar_2, 0, 0, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12)) [ ar_1 >= ar_2 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f19(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) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3 + n, ar_4 + 1, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12)) [ ar_1 >= ar_4 /\ ar_4 >= ar_2 + 1 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f19(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) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3 + n, ar_4 + 1, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12)) [ ar_2 >= ar_4 + 1 /\ ar_1 >= ar_4 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f19(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) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3 + n, ar_2 + 1, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12)) [ ar_1 >= ar_4 /\ ar_2 = ar_4 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f33(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) -> Com_1(f36(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_6 + 1, ar_8, ar_9, ar_10, ar_11, ar_12)) [ ar_5 >= ar_6 + 1 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f36(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) -> Com_1(f41(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, n, 0, ar_10, ar_11, ar_12)) [ 0 >= ar_6 + 1 /\ ar_5 >= ar_7 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f36(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) -> Com_1(f41(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, n, 0, ar_10, ar_11, ar_12)) [ ar_6 >= 1 /\ ar_5 >= ar_7 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f41(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) -> Com_1(f41(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, n, ar_9 + 1, ar_10, ar_11, ar_12)) [ ar_6 >= ar_9 + 1 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f36(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) -> Com_1(f36(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, 0, ar_7 + 1, n, ar_9, ar_10, ar_11, ar_12)) [ ar_5 >= ar_7 /\ ar_6 = 0 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f50(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) -> Com_1(f54(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, n, 0, ar_10, ar_11, ar_12)) [ ar_5 >= ar_7 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f54(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) -> Com_1(f54(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, n, ar_9 + 1, ar_10, ar_11, ar_12)) [ ar_6 >= ar_9 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f66(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) -> Com_1(f70(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, 0, n, ar_9, ar_10, ar_11, ar_12)) [ ar_5 >= ar_6 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f70(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) -> Com_1(f70(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7 + 1, n, ar_9, ar_10, ar_11, ar_12)) [ ar_6 >= ar_7 + 1 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f80(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) -> Com_1(f84(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_6 + 1, n, ar_9, ar_10, ar_11, ar_12)) [ ar_6 >= 0 ] 7.70/2.93 7.70/2.93 (Comp: ?, Cost: 1) f84(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) -> Com_1(f84(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7 + 1, n, ar_9, ar_10, ar_11, ar_12)) [ ar_5 >= ar_7 ] 7.70/2.94 7.70/2.94 (Comp: ?, Cost: 1) f84(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) -> Com_1(f80(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6 - 1, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12)) [ ar_7 >= ar_5 + 1 ] 7.70/2.94 7.70/2.94 (Comp: ?, Cost: 1) f80(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) -> Com_1(f96(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, 0, 0, ar_12)) [ 0 >= ar_6 + 1 ] 7.70/2.94 7.70/2.94 (Comp: ?, Cost: 1) f70(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) -> Com_1(f66(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6 + 1, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12)) [ ar_7 >= ar_6 ] 7.70/2.94 7.70/2.94 (Comp: ?, Cost: 1) f66(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) -> Com_1(f80(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_5 - 1, ar_7, ar_8, ar_9, ar_10, ar_11, ar_12)) [ ar_6 >= ar_5 + 1 ] 7.70/2.94 7.70/2.94 (Comp: ?, Cost: 1) f54(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) -> Com_1(f50(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7 + 1, ar_8, ar_9, ar_10, ar_11, ar_12)) [ ar_9 >= ar_6 + 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