Complexity_ITS 2019-03-21 04.46 pair #429990826

details
property	value
status	complete
benchmark	graycode.koat
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n125.star.cs.uiowa.edu
space	T2
run statistics
property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	7.8219 seconds
cpu usage	19.7679
user time	19.1053
system time	0.662658
max virtual memory	1.895988E7
max residence set size	317332.0
stage attributes
key	value
starexec-result	WORST_CASE(?, O(1))
output
19.50/7.07	WORST_CASE(?, O(1))
19.50/7.09	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
19.50/7.09	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
19.50/7.09	
19.50/7.09	
19.50/7.09	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, 1).
19.50/7.09	
19.50/7.09	(0) CpxIntTrs
19.50/7.09	(1) Koat Proof [FINISHED, 5306 ms]
19.50/7.09	(2) BOUNDS(1, 1)
19.50/7.09	
19.50/7.09	
19.50/7.09	----------------------------------------
19.50/7.09	
19.50/7.09	(0)
19.50/7.09	Obligation:
19.50/7.09	Complexity Int TRS consisting of the following rules:
19.50/7.09	f62(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
19.50/7.09	f62(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
19.50/7.09	f0(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f13(1, 12, 1, 1, M, 0, G, H, I, J, K, L)) :|: TRUE
19.50/7.09	f13(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f13(A, B, C, D, E, F + 1, G, H, I, J, K, L)) :|: B >= F + 1
19.50/7.09	f19(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f22(A, B, C, D, E, F, G, H, I, J, K, L)) :|: 0 >= C + 1 && B >= F + 1
19.50/7.09	f19(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f22(A, B, C, D, E, F, G, H, I, J, K, L)) :|: C >= 1 && B >= F + 1
19.50/7.09	f22(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f19(A, B, 1, D, E, F + 1, 1, H, I, J, K, L)) :|: M >= 0 && B >= N + 1
19.50/7.09	f22(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f19(A, B, 0, D, E, F + 1, 0, H, I, J, K, L)) :|: M >= 0
19.50/7.09	f22(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f19(A, B, 0, D, E, F + 1, 0, H, I, J, K, L)) :|: 0 >= M + 1
19.50/7.09	f19(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f19(A, B, 0, D, E, F + 1, 0, H, I, J, K, L)) :|: B >= F + 1 && C >= 0 && C <= 0
19.50/7.09	f32(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f35(A, B, C, D, E, F, G, F + 1, I, J, K, L)) :|: B >= 2 + F
19.50/7.09	f35(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f38(A, B, C, D, E, F, G, H, I, J, K, L)) :|: 0 >= A + 1 && B >= H + 1
19.50/7.09	f35(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f38(A, B, C, D, E, F, G, H, I, J, K, L)) :|: A >= 1 && B >= H + 1
19.50/7.09	f38(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f35(1, B, C, D, E, F, G, H + 1, 1, J, K, L)) :|: M >= N + 1
19.50/7.09	f38(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f35(1, B, C, D, E, F, G, H + 1, 1, J, K, L)) :|: TRUE
19.50/7.09	f38(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f35(0, B, C, D, E, F, G, H + 1, 0, J, K, L)) :|: TRUE
19.50/7.09	f35(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f35(0, B, C, D, E, F, G, H + 1, 0, J, K, L)) :|: B >= H + 1 && A >= 0 && A <= 0
19.50/7.09	f48(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f52(A, B, C, D, E, F, G, H, I, M, K, L)) :|: 0 >= D + 1 && B >= 2 + F
19.50/7.09	f48(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f52(A, B, C, D, E, F, G, H, I, M, K, L)) :|: D >= 1 && B >= 2 + F
19.50/7.09	f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f48(A, B, C, 1, E, F + 1, G, H, I, J, 1, L)) :|: 0 >= J + 1
19.50/7.09	f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f48(A, B, C, 1, E, F + 1, G, H, I, J, 1, L)) :|: J >= 1
19.50/7.09	f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f48(A, B, C, 0, E, F + 1, G, H, I, 0, 0, L)) :|: J >= 0 && J <= 0
19.50/7.09	f52(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f48(A, B, C, 0, E, F + 1, G, H, I, J, 0, L)) :|: TRUE
19.50/7.09	f48(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f48(A, B, C, 0, E, F + 1, G, H, I, M, 0, L)) :|: B >= 2 + F && D >= 0 && D <= 0
19.50/7.09	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 >= D + 1
19.50/7.09	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)) :|: D >= 1
19.50/7.09	f63(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f71(A, B, C, 0, E, F, G, H, I, J, K, 1)) :|: D >= 0 && D <= 0
19.50/7.09	f62(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)) :|: A >= 0 && A <= 0
19.50/7.09	f48(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f62(A, B, C, D, E, F, G, H, I, J, K, L)) :|: 0 >= C + 1 && F + 1 >= B
19.50/7.09	f48(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f62(A, B, C, D, E, F, G, H, I, J, K, L)) :|: C >= 1 && F + 1 >= B
19.50/7.09	f48(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f71(A, B, 0, D, E, F, G, H, I, J, K, 1)) :|: F + 1 >= B && C >= 0 && C <= 0
19.50/7.09	f35(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f32(A, B, C, D, E, F + 1, G, H, I, J, K, L)) :|: H >= B
19.50/7.09	f32(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f48(A, B, C, D, E, 0, G, H, I, J, K, L)) :|: F + 1 >= B
19.50/7.09	f19(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f32(A, B, C, D, E, 0, G, H, I, J, K, L)) :|: F >= B
19.50/7.09	f13(A, B, C, D, E, F, G, H, I, J, K, L) -> Com_1(f19(A, B, C, D, E, 0, G, H, I, J, K, L)) :|: F >= B
19.50/7.09	
19.50/7.09	The start-symbols are:[f0_12]
19.50/7.09	
19.50/7.09	
19.50/7.09	----------------------------------------
19.50/7.09	
19.50/7.09	(1) Koat Proof (FINISHED)
19.50/7.09	YES(?, 234911365)
19.50/7.09	
19.50/7.09	
19.50/7.09	
19.50/7.09	Initial complexity problem:
19.50/7.09	
19.50/7.09	1:	T:
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f62(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 ]
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f62(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 ]
19.50/7.09	
19.50/7.09			(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(f13(1, 12, 1, 1, m, 0, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11))
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f13(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(f13(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_1 >= ar_5 + 1 ]
19.50/7.09	
19.50/7.09			(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) -> Com_1(f22(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_2 + 1 /\ ar_1 >= ar_5 + 1 ]
19.50/7.09	
19.50/7.09			(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) -> Com_1(f22(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_2 >= 1 /\ ar_1 >= ar_5 + 1 ]
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f22(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(f19(ar_0, ar_1, 1, ar_3, ar_4, ar_5 + 1, 1, ar_7, ar_8, ar_9, ar_10, ar_11)) [ m >= 0 /\ ar_1 >= n + 1 ]
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f22(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(f19(ar_0, ar_1, 0, ar_3, ar_4, ar_5 + 1, 0, ar_7, ar_8, ar_9, ar_10, ar_11)) [ m >= 0 ]
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f22(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(f19(ar_0, ar_1, 0, ar_3, ar_4, ar_5 + 1, 0, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 0 >= m + 1 ]
19.50/7.09	
19.50/7.09			(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) -> Com_1(f19(ar_0, ar_1, 0, ar_3, ar_4, ar_5 + 1, 0, ar_7, ar_8, ar_9, ar_10, ar_11)) [ ar_1 >= ar_5 + 1 /\ ar_2 = 0 ]
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f32(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(f35(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_5 + 1, ar_8, ar_9, ar_10, ar_11)) [ ar_1 >= ar_5 + 2 ]
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f35(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(f38(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_1 >= ar_7 + 1 ]
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f35(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(f38(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_1 >= ar_7 + 1 ]
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f38(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(f35(1, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7 + 1, 1, ar_9, ar_10, ar_11)) [ m >= n + 1 ]
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f38(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(f35(1, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7 + 1, 1, ar_9, ar_10, ar_11))
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f38(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(f35(0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7 + 1, 0, ar_9, ar_10, ar_11))
19.50/7.09	
19.50/7.09			(Comp: ?, Cost: 1)    f35(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(f35(0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7 + 1, 0, ar_9, ar_10, ar_11)) [ ar_1 >= ar_7 + 1 /\ ar_0 = 0 ]
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