Complexity_ITS 2019-03-21 04.46 pair #429989950

details
property	value
status	complete
benchmark	perfect2.c.koat
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n074.star.cs.uiowa.edu
space	Flores-Montoya_16
run statistics
property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	11.1686 seconds
cpu usage	16.4319
user time	15.6182
system time	0.813737
max virtual memory	1.8811712E7
max residence set size	227380.0
stage attributes
key	value
starexec-result	WORST_CASE(Omega(n^1), O(n^2))
output
16.20/11.11	WORST_CASE(Omega(n^1), O(n^2))
16.20/11.13	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
16.20/11.13	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.20/11.13	
16.20/11.13	
16.20/11.13	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(7 + Arg_0 * max(18, 9 * Arg_0), 7) + nat(Arg_0 * max(18, 9 * Arg_0)) * nat(Arg_0) + max(3, 3 * Arg_0) * nat(Arg_0) + max(6 * Arg_0, 6) + nat(7 * Arg_0) + max(3, 3 + Arg_0)).
16.20/11.13	
16.20/11.13	(0) CpxIntTrs
16.20/11.13	(1) Loat Proof [FINISHED, 1817 ms]
16.20/11.13	(2) BOUNDS(n^1, INF)
16.20/11.13	
16.20/11.13	
16.20/11.13	----------------------------------------
16.20/11.13	
16.20/11.13	(0)
16.20/11.13	Obligation:
16.20/11.13	Complexity Int TRS consisting of the following rules:
16.20/11.13	eval_perfect2_start(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb0_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.20/11.13	eval_perfect2_bb0_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_0(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.20/11.13	eval_perfect2_0(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_1(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.20/11.13	eval_perfect2_1(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb3_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_x <= 0
16.20/11.13	eval_perfect2_1(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb1_in(v__y3_0, v_1, v_8, v_x, v_x, v_y2_1, v_x)) :|: v_x > 0
16.20/11.13	eval_perfect2_bb1_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb2_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y1_0 - 1 >= 0 && v_y1_0 - 1 <= 0
16.20/11.13	eval_perfect2_bb1_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb4_in(v__y3_0, v_y1_0 - 1, v_8, v_x, v_y1_0, v_x, v_y3_0)) :|: v_y1_0 - 1 < 0
16.20/11.13	eval_perfect2_bb1_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb4_in(v__y3_0, v_y1_0 - 1, v_8, v_x, v_y1_0, v_x, v_y3_0)) :|: v_y1_0 - 1 > 0
16.20/11.13	eval_perfect2_bb2_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb3_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 < 0
16.20/11.13	eval_perfect2_bb2_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb3_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 > 0
16.20/11.13	eval_perfect2_bb2_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb3_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 >= 0 && v_y3_0 <= 0
16.20/11.13	eval_perfect2_bb3_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_stop(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.20/11.13	eval_perfect2_bb4_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb5_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 >= v_1
16.20/11.13	eval_perfect2_bb4_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb6_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 < v_1
16.20/11.13	eval_perfect2_bb5_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb4_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1 - v_1, v_y3_0)) :|: TRUE
16.20/11.13	eval_perfect2_bb6_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_9(v__y3_0, v_1, v_y3_0 - v_1, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.20/11.13	eval_perfect2_9(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_10(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.20/11.13	eval_perfect2_10(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_11(v_8, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 >= 0 && v_y2_1 <= 0
16.20/11.13	eval_perfect2_10(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_11(v_y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 < 0
16.20/11.13	eval_perfect2_10(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_11(v_y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 > 0
16.20/11.13	eval_perfect2_11(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_12(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.20/11.13	eval_perfect2_12(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect2_bb1_in(v__y3_0, v_1, v_8, v_x, v_1, v_y2_1, v__y3_0)) :|: TRUE
16.20/11.13	
16.20/11.13	The start-symbols are:[eval_perfect2_start_7]
16.20/11.13	
16.20/11.13	
16.20/11.13	----------------------------------------
16.20/11.13	
16.20/11.13	(1) Loat Proof (FINISHED)
16.20/11.13	
16.20/11.13	
16.20/11.13	### Pre-processing the ITS problem ###
16.20/11.13	
16.20/11.13	
16.20/11.13	
16.20/11.13	Initial linear ITS problem
16.20/11.13	
16.20/11.13	   Start location: evalperfect2start
16.20/11.13	
16.20/11.13	      0: evalperfect2start -> evalperfect2bb0in : [], cost: 1
16.20/11.13	
16.20/11.13	      1: evalperfect2bb0in -> evalperfect20 : [], cost: 1
16.20/11.13	
16.20/11.13	      2: evalperfect20 -> evalperfect21 : [], cost: 1
16.20/11.13	
16.20/11.13	      3: evalperfect21 -> evalperfect2bb3in : [ 0>=A ], cost: 1
16.20/11.13	
16.20/11.13	      4: evalperfect21 -> evalperfect2bb1in : B'=A, C'=A, [ A>=1 ], cost: 1
16.20/11.13	
16.20/11.13	      5: evalperfect2bb1in -> evalperfect2bb2in : [ B==1 ], cost: 1
16.20/11.13	
16.20/11.13	      6: evalperfect2bb1in -> evalperfect2bb4in : D'=-1+B, E'=A, [ 0>=B ], cost: 1
16.20/11.13	
16.20/11.13	      7: evalperfect2bb1in -> evalperfect2bb4in : D'=-1+B, E'=A, [ B>=2 ], cost: 1
16.20/11.13	
16.20/11.13	      8: evalperfect2bb2in -> evalperfect2bb3in : [ 0>=1+C ], cost: 1
16.20/11.13	
16.20/11.13	      9: evalperfect2bb2in -> evalperfect2bb3in : [ C>=1 ], cost: 1
16.20/11.13	
16.20/11.13	     10: evalperfect2bb2in -> evalperfect2bb3in : [ C==0 ], cost: 1
16.20/11.13	
16.20/11.13	     11: evalperfect2bb3in -> evalperfect2stop : [], cost: 1
16.20/11.13	
16.20/11.13	     12: evalperfect2bb4in -> evalperfect2bb5in : [ E>=D ], cost: 1
16.20/11.13	
16.20/11.13	     13: evalperfect2bb4in -> evalperfect2bb6in : [ D>=1+E ], cost: 1
16.20/11.13	
16.20/11.13	     14: evalperfect2bb5in -> evalperfect2bb4in : E'=-D+E, [], cost: 1
16.20/11.13	
16.20/11.13	     15: evalperfect2bb6in -> evalperfect29 : F'=C-D, [], cost: 1
16.20/11.13	
16.20/11.13	     16: evalperfect29 -> evalperfect210 : [], cost: 1
16.20/11.13	
16.20/11.13	     17: evalperfect210 -> evalperfect211 : G'=F, [ E==0 ], cost: 1
16.20/11.13	
16.20/11.13	     18: evalperfect210 -> evalperfect211 : G'=C, [ 0>=1+E ], cost: 1
16.20/11.13	
16.20/11.13	     19: evalperfect210 -> evalperfect211 : G'=C, [ E>=1 ], cost: 1
16.20/11.13	
16.20/11.13	     20: evalperfect211 -> evalperfect212 : [], cost: 1
16.20/11.13	
16.20/11.13	     21: evalperfect212 -> evalperfect2bb1in : B'=D, C'=G, [], cost: 1
16.20/11.13
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