Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Complexity_ITS 2019-03-21 04.46 pair #429990790
details
property
value
status
complete
benchmark
sort.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n123.star.cs.uiowa.edu
space
T2
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
2.6276 seconds
cpu usage
6.33634
user time
5.94389
system time
0.392453
max virtual memory
1.8757028E7
max residence set size
231744.0
stage attributes
key
value
starexec-result
WORST_CASE(?, O(1))
output
6.18/2.57 WORST_CASE(?, O(1)) 6.18/2.58 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 6.18/2.58 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.18/2.58 6.18/2.58 6.18/2.58 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, 1). 6.18/2.58 6.18/2.58 (0) CpxIntTrs 6.18/2.58 (1) Koat Proof [FINISHED, 782 ms] 6.18/2.58 (2) BOUNDS(1, 1) 6.18/2.58 6.18/2.58 6.18/2.58 ---------------------------------------- 6.18/2.58 6.18/2.58 (0) 6.18/2.58 Obligation: 6.18/2.58 Complexity Int TRS consisting of the following rules: 6.18/2.58 f0(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f23(1, 1, 10, M, N, 0, G, H, I, J, K, L)) :|: TRUE 6.18/2.58 f23(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f23(A, B, C, D, E, F + 1, G, H, I, J, K, L)) :|: C >= F + 1 6.18/2.58 f29(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f33(A, B, C, D, E, F, 0, 0, I, J, K, L)) :|: C >= F + 1 6.18/2.58 f33(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f33(A, B, C, D, E, F, 1, H + 1, 1, J, K, L)) :|: 0 >= G + 1 && C >= H + 1 6.18/2.58 f33(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f33(A, B, C, D, E, F, 1, H + 1, 1, J, K, L)) :|: G >= 1 && C >= H + 1 6.18/2.58 f33(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f33(A, B, C, D, E, F, 1, H + 1, 1, J, K, L)) :|: C >= H + 1 && G >= 0 && G <= 0 6.18/2.58 f33(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f33(A, B, C, D, E, F, 0, H + 1, 0, J, K, L)) :|: M >= N + 1 && C >= H + 1 && G >= 0 && G <= 0 6.18/2.58 f33(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f33(A, B, C, D, E, F, 0, H + 1, 0, J, K, L)) :|: C >= H + 1 && G >= 0 && G <= 0 6.18/2.58 f44(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f29(1, B, C, D, E, F + 1, G, H, I, 1, K, L)) :|: 0 >= G + 1 6.18/2.58 f44(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f29(1, B, C, D, E, F + 1, G, H, I, 1, K, L)) :|: G >= 1 6.18/2.58 f44(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f29(0, B, C, D, E, F + 1, 0, H, I, 0, K, L)) :|: G >= 0 && G <= 0 6.18/2.58 f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f55(A, B, C, D, E, F, G, H, I, J, K, L)) :|: 0 >= B + 1 && C >= 2 + F 6.18/2.58 f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f55(A, B, C, D, E, F, G, H, I, J, K, L)) :|: B >= 1 && C >= 2 + F 6.18/2.58 f55(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f52(A, 1, C, D, E, F + 1, G, H, I, J, 1, L)) :|: M >= N + 1 6.18/2.58 f55(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f52(A, 0, C, D, E, F + 1, G, H, I, J, 0, L)) :|: TRUE 6.18/2.58 f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f52(A, 0, C, D, E, F + 1, G, H, I, J, 0, L)) :|: C >= 2 + F && B >= 0 && B <= 0 6.18/2.58 f63(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f71(A, B, C, D, E, F, G, H, I, J, K, 0)) :|: 0 >= B + 1 6.18/2.58 f63(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f71(A, B, C, D, E, F, G, H, I, J, K, 0)) :|: B >= 1 6.18/2.58 f63(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f71(A, 0, C, D, E, F, G, H, I, J, K, 1)) :|: B >= 0 && B <= 0 6.18/2.58 f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f63(A, B, C, D, E, F, G, H, I, J, K, L)) :|: 0 >= A + 1 && F + 1 >= C 6.18/2.58 f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f63(A, B, C, D, E, F, G, H, I, J, K, L)) :|: A >= 1 && F + 1 >= C 6.18/2.58 f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f71(0, B, C, D, E, F, G, H, I, J, K, 1)) :|: F + 1 >= C && A >= 0 && A <= 0 6.18/2.58 f33(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f44(A, B, C, D, E, F, G, H, I, J, K, L)) :|: 0 >= A + 1 && H >= C 6.18/2.58 f33(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f44(A, B, C, D, E, F, G, H, I, J, K, L)) :|: A >= 1 && H >= C 6.18/2.58 f33(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f29(0, B, C, D, E, F + 1, G, H, I, 0, K, L)) :|: H >= C && A >= 0 && A <= 0 6.18/2.58 f29(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f52(A, B, C, D, E, 0, G, H, I, J, K, L)) :|: F >= C 6.18/2.58 f23(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f29(A, B, C, D, E, 0, G, H, I, J, K, L)) :|: F >= C 6.18/2.58 6.18/2.58 The start-symbols are:[f0_12] 6.18/2.58 6.18/2.58 6.18/2.58 ---------------------------------------- 6.18/2.58 6.18/2.58 (1) Koat Proof (FINISHED) 6.18/2.58 YES(?, 3005) 6.18/2.58 6.18/2.58 6.18/2.58 6.18/2.58 Initial complexity problem: 6.18/2.58 6.18/2.58 1: T: 6.18/2.58 6.18/2.58 (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) -> Com_1(f23(1, 1, 10, m, n, 0, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f23(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f23(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ ar_2 >= ar_5 + 1 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f29(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f33(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, 0, 0, ar_8, ar_9, ar_10, ar_11)) [ ar_2 >= ar_5 + 1 ] 6.18/2.58 6.18/2.58 (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) -> Com_1(f33(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, 1, ar_7 + 1, 1, ar_9, ar_10, ar_11)) [ 0 >= ar_6 + 1 /\ ar_2 >= ar_7 + 1 ] 6.18/2.58 6.18/2.58 (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) -> Com_1(f33(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, 1, ar_7 + 1, 1, ar_9, ar_10, ar_11)) [ ar_6 >= 1 /\ ar_2 >= ar_7 + 1 ] 6.18/2.58 6.18/2.58 (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) -> Com_1(f33(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, 1, ar_7 + 1, 1, ar_9, ar_10, ar_11)) [ ar_2 >= ar_7 + 1 /\ ar_6 = 0 ] 6.18/2.58 6.18/2.58 (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) -> Com_1(f33(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, 0, ar_7 + 1, 0, ar_9, ar_10, ar_11)) [ m >= n + 1 /\ ar_2 >= ar_7 + 1 /\ ar_6 = 0 ] 6.18/2.58 6.18/2.58 (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) -> Com_1(f33(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, 0, ar_7 + 1, 0, ar_9, ar_10, ar_11)) [ ar_2 >= ar_7 + 1 /\ ar_6 = 0 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f44(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f29(1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7, ar_8, 1, ar_10, ar_11)) [ 0 >= ar_6 + 1 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f44(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f29(1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7, ar_8, 1, ar_10, ar_11)) [ ar_6 >= 1 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f44(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f29(0, ar_1, ar_2, ar_3, ar_4, ar_5 + 1, 0, ar_7, ar_8, 0, ar_10, ar_11)) [ ar_6 = 0 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f55(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 0 >= ar_1 + 1 /\ ar_2 >= ar_5 + 2 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f55(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_1 >= 1 /\ ar_2 >= ar_5 + 2 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f55(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f52(ar_0, 1, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7, ar_8, ar_9, 1, ar_11)) [ m >= n + 1 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f55(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f52(ar_0, 0, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7, ar_8, ar_9, 0, ar_11)) 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f52(ar_0, 0, ar_2, ar_3, ar_4, ar_5 + 1, ar_6, ar_7, ar_8, ar_9, 0, ar_11)) [ ar_2 >= ar_5 + 2 /\ ar_1 = 0 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f63(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, 0)) [ 0 >= ar_1 + 1 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f63(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, 0)) [ ar_1 >= 1 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f63(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f71(ar_0, 0, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, 1)) [ ar_1 = 0 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f63(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 0 >= ar_0 + 1 /\ ar_5 + 1 >= ar_2 ] 6.18/2.58 6.18/2.58 (Comp: ?, Cost: 1) f52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(f63(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_0 >= 1 /\ ar_5 + 1 >= ar_2 ]
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