details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	59.9333 seconds
cpu usage	76.8541
user time	75.7869
system time	1.06722
max virtual memory	1.903212E7
max residence set size	308404.0

stage attributes

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

output

76.66/59.89 WORST_CASE(Omega(n^1), ?) 76.79/59.90 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 76.79/59.90 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 76.79/59.90 76.79/59.90 76.79/59.90 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, INF). 76.79/59.90 76.79/59.90 (0) CpxIntTrs 76.79/59.90 (1) Loat Proof [FINISHED, 9332 ms] 76.79/59.90 (2) BOUNDS(n^1, INF) 76.79/59.90 76.79/59.90 76.79/59.90 ---------------------------------------- 76.79/59.90 76.79/59.90 (0) 76.79/59.90 Obligation: 76.79/59.90 Complexity Int TRS consisting of the following rules: 76.79/59.90 f13(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, E, F, G, H, I, J)) :|: 0 >= K + 1 76.79/59.90 f13(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, E, F, G, H, I, J)) :|: K >= 1 76.79/59.90 f13(A, B, C, D, E, F, G, H, I, J) -> Com_1(f29(L, 0, -(2) + D, -(1) + D, E, F, G, H, I, J)) :|: TRUE 76.79/59.90 f19(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, E, F, G, H, I, J)) :|: 0 >= K + 1 76.79/59.90 f19(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, E, F, G, H, I, J)) :|: K >= 1 76.79/59.90 f19(A, B, C, D, E, F, G, H, I, J) -> Com_1(f29(L, 0, -(2) + D, -(1) + D, E, F, G, H, I, J)) :|: TRUE 76.79/59.90 f8(A, B, C, D, E, F, G, H, I, J) -> Com_1(f27(A, B, C, D, 0, 0, G, H, I, J)) :|: TRUE 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f27(L, 0, -(2) + D, -(1) + D, 0, F, 0, H, I, J)) :|: D >= 1 && C + D >= 1 && C >= 1 && E >= 0 && E <= 0 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f27(L, K, -(1) + C, -(1) + C, 0, F, 0, H, I, J)) :|: D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 0 && E <= 0 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f27(L, K, -(1) + C, -(1) + C, 0, F, 0, H, I, J)) :|: D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 0 && E <= 0 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, M, C, D, J)) :|: D >= 1 && C >= 1 && C + D >= 1 && 0 >= K + 1 && 0 >= M + 1 && E >= 0 && E <= 0 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, M, C, D, J)) :|: D >= 1 && C >= 1 && C + D >= 1 && 0 >= K + 1 && M >= 1 && E >= 0 && E <= 0 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, M, C, D, J)) :|: D >= 1 && C >= 1 && C + D >= 1 && K >= 1 && 0 >= M + 1 && E >= 0 && E <= 0 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, M, C, D, J)) :|: D >= 1 && C >= 1 && C + D >= 1 && K >= 1 && M >= 1 && E >= 0 && E <= 0 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f28(L, 0, -(2) + D, -(1) + D, 1, F, K, C, D, J)) :|: D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 0 && E <= 0 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f28(L, 0, -(2) + D, -(1) + D, 1, F, K, C, D, J)) :|: D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 0 && E <= 0 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f9(A, B, C, D, E, F, G, H, I, L)) :|: 0 >= C 76.79/59.90 f27(A, B, C, D, E, F, G, H, I, J) -> Com_1(f9(A, B, C, D, E, F, G, H, I, L)) :|: C >= 1 && 0 >= D 76.79/59.90 f28(A, B, C, D, E, F, G, H, I, J) -> Com_1(f300(A, B, C, D, 1, 1, G, H, I, J)) :|: D >= I && C >= H && C + D >= H + I && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f28(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f28(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f28(A, B, C, D, E, F, G, H, I, J) -> Com_1(f28(L, 0, -(2) + D, -(1) + D, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f28(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f28(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f28(A, B, C, D, E, F, G, H, I, J) -> Com_1(f28(L, 0, -(2) + D, -(1) + D, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f28(A, B, C, D, E, F, G, H, I, J) -> Com_1(f9(A, B, C, D, E, F, G, H, I, L)) :|: 0 >= C 76.79/59.90 f28(A, B, C, D, E, F, G, H, I, J) -> Com_1(f9(A, B, C, D, E, F, G, H, I, L)) :|: C >= 1 && 0 >= D 76.79/59.90 f29(A, B, C, D, E, F, G, H, I, J) -> Com_1(f300(A, B, C, D, 1, 1, G, H, I, J)) :|: D >= I && C >= H && C + D >= H + I && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f29(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f29(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f29(A, B, C, D, E, F, G, H, I, J) -> Com_1(f29(L, 0, -(2) + D, -(1) + D, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f29(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f29(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f29(A, B, C, D, E, F, G, H, I, J) -> Com_1(f29(L, 0, -(2) + D, -(1) + D, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f29(A, B, C, D, E, F, G, H, I, J) -> Com_1(f9(A, B, C, D, E, F, G, H, I, L)) :|: 0 >= C 76.79/59.90 f29(A, B, C, D, E, F, G, H, I, J) -> Com_1(f9(A, B, C, D, E, F, G, H, I, L)) :|: C >= 1 && 0 >= D 76.79/59.90 f30(A, B, C, D, E, F, G, H, I, J) -> Com_1(f300(A, B, C, D, 1, 1, G, H, I, J)) :|: D >= I && C >= H && C + D >= H + I && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f30(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f30(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f30(A, B, C, D, E, F, G, H, I, J) -> Com_1(f28(L, 0, -(2) + D, -(1) + D, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f30(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f30(A, B, C, D, E, F, G, H, I, J) -> Com_1(f30(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f30(A, B, C, D, E, F, G, H, I, J) -> Com_1(f28(L, 0, -(2) + D, -(1) + D, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f30(A, B, C, D, E, F, G, H, I, J) -> Com_1(f9(A, B, C, D, E, F, G, H, I, L)) :|: 0 >= C 76.79/59.90 f31(A, B, C, D, E, F, G, H, I, J) -> Com_1(f300(A, B, C, D, 1, 1, G, H, I, J)) :|: D >= I && C >= H && C + D >= H + I && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f31(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f31(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f31(A, B, C, D, E, F, G, H, I, J) -> Com_1(f29(L, 0, -(2) + D, -(1) + D, 1, F, G, H, I, J)) :|: H >= C + 1 && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f31(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C >= 1 && 0 >= K + 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f31(A, B, C, D, E, F, G, H, I, J) -> Com_1(f31(L, K, -(1) + C, -(1) + C, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C >= 1 && K >= 1 && C + D >= 1 && E >= 1 && E <= 1 76.79/59.90 f31(A, B, C, D, E, F, G, H, I, J) -> Com_1(f29(L, 0, -(2) + D, -(1) + D, 1, F, G, H, I, J)) :|: I >= D + 1 && C >= H && D >= 1 && C + D >= 1 && C >= 1 && E >= 1 && E <= 1 76.79/59.90 f31(A, B, C, D, E, F, G, H, I, J) -> Com_1(f9(A, B, C, D, E, F, G, H, I, L)) :|: 0 >= C 76.79/59.90 76.79/59.90 The start-symbols are:[f8_10] 76.79/59.90 76.79/59.90 76.79/59.90 ---------------------------------------- 76.79/59.90 76.79/59.90 (1) Loat Proof (FINISHED) 76.79/59.90 76.79/59.90 76.79/59.90 ### Pre-processing the ITS problem ### 76.79/59.90 76.79/59.90 76.79/59.90 76.79/59.90 Initial linear ITS problem 76.79/59.90 76.79/59.90 Start location: f8 76.79/59.90 76.79/59.90 0: f13 -> f31 : A'=free, B'=free_1, C'=-1+C, D'=-1+C, [ 0>=1+free_1 ], cost: 1 76.79/59.90 76.79/59.90 1: f13 -> f31 : A'=free_2, B'=free_3, C'=-1+C, D'=-1+C, [ free_3>=1 ], cost: 1 76.79/59.90 76.79/59.90 2: f13 -> f29 : A'=free_4, B'=0, C'=-2+D, D'=-1+D, [], cost: 1 76.79/59.90 76.79/59.90 3: f19 -> f31 : A'=free_5, B'=free_6, C'=-1+C, D'=-1+C, [ 0>=1+free_6 ], cost: 1 76.79/59.90 76.79/59.90 4: f19 -> f31 : A'=free_7, B'=free_8, C'=-1+C, D'=-1+C, [ free_8>=1 ], cost: 1 76.79/59.90 76.79/59.90 5: f19 -> f29 : A'=free_9, B'=0, C'=-2+D, D'=-1+D, [], cost: 1 76.79/59.90 76.79/59.90 6: f8 -> f27 : E'=0, F'=0, [], cost: 1 76.79/59.90 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