Complexity_ITS 2019-03-21 04.46 pair #429989856

details
property	value
status	complete
benchmark	unperfect.c.koat
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n070.star.cs.uiowa.edu
space	Flores-Montoya_16
run statistics
property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	10.996 seconds
cpu usage	16.2518
user time	15.5264
system time	0.725381
max virtual memory	1.8849516E7
max residence set size	229044.0
stage attributes
key	value
starexec-result	WORST_CASE(Omega(n^1), O(n^2))
output
16.11/10.94	WORST_CASE(Omega(n^1), O(n^2))
16.11/10.96	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
16.11/10.96	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.11/10.96	
16.11/10.96	
16.11/10.96	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(7, 7 + Arg_0 * max(6, 3 * Arg_0)) + nat(Arg_0 * max(6, 3 * Arg_0)) * nat(Arg_0) + max(3, 3 * Arg_0) * nat(Arg_0) + max(3, 3 * Arg_0) + nat(6 * Arg_0) + nat(2 * Arg_0) + max(3, 3 + Arg_0)).
16.11/10.96	
16.11/10.96	(0) CpxIntTrs
16.11/10.96	(1) Loat Proof [FINISHED, 1853 ms]
16.11/10.96	(2) BOUNDS(n^1, INF)
16.11/10.96	
16.11/10.96	
16.11/10.96	----------------------------------------
16.11/10.96	
16.11/10.96	(0)
16.11/10.96	Obligation:
16.11/10.96	Complexity Int TRS consisting of the following rules:
16.11/10.96	eval_unperfect_start(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_bb0_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.11/10.96	eval_unperfect_bb0_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_0(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.11/10.96	eval_unperfect_0(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_1(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.11/10.96	eval_unperfect_1(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_bb3_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_x <= 0
16.11/10.96	eval_unperfect_1(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_bb1_in(v__y3_0, v_1, v_8, v_x, v_x, v_y2_1, v_x)) :|: v_x > 0
16.11/10.96	eval_unperfect_bb1_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_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.11/10.96	eval_unperfect_bb1_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_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.11/10.96	eval_unperfect_bb1_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_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.11/10.96	eval_unperfect_bb2_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_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.11/10.96	eval_unperfect_bb2_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_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.11/10.96	eval_unperfect_bb2_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_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.11/10.96	eval_unperfect_bb3_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_stop(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.11/10.96	eval_unperfect_bb4_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_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.11/10.96	eval_unperfect_bb4_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_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.11/10.96	eval_unperfect_bb5_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_bb4_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1 - v_1, v_y3_0)) :|: TRUE
16.11/10.96	eval_unperfect_bb6_in(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_9(v__y3_0, v_1, v_y3_0 - v_1, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.11/10.96	eval_unperfect_9(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_10(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.11/10.96	eval_unperfect_10(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_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.11/10.96	eval_unperfect_10(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_11(v_y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 < 0
16.11/10.96	eval_unperfect_10(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_11(v_y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 > 0
16.11/10.96	eval_unperfect_11(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_12(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
16.11/10.96	eval_unperfect_12(v__y3_0, v_1, v_8, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_unperfect_bb1_in(v__y3_0, v_1, v_8, v_x, v_1, v_y2_1, v__y3_0)) :|: TRUE
16.11/10.96	
16.11/10.96	The start-symbols are:[eval_unperfect_start_7]
16.11/10.96	
16.11/10.96	
16.11/10.96	----------------------------------------
16.11/10.96	
16.11/10.96	(1) Loat Proof (FINISHED)
16.11/10.96	
16.11/10.96	
16.11/10.96	### Pre-processing the ITS problem ###
16.11/10.96	
16.11/10.96	
16.11/10.96	
16.11/10.96	Initial linear ITS problem
16.11/10.96	
16.11/10.96	   Start location: evalunperfectstart
16.11/10.96	
16.11/10.96	      0: evalunperfectstart -> evalunperfectbb0in : [], cost: 1
16.11/10.96	
16.11/10.96	      1: evalunperfectbb0in -> evalunperfect0 : [], cost: 1
16.11/10.96	
16.11/10.96	      2: evalunperfect0 -> evalunperfect1 : [], cost: 1
16.11/10.96	
16.11/10.96	      3: evalunperfect1 -> evalunperfectbb3in : [ 0>=A ], cost: 1
16.11/10.96	
16.11/10.96	      4: evalunperfect1 -> evalunperfectbb1in : B'=A, C'=A, [ A>=1 ], cost: 1
16.11/10.96	
16.11/10.96	      5: evalunperfectbb1in -> evalunperfectbb2in : [ B==1 ], cost: 1
16.11/10.96	
16.11/10.96	      6: evalunperfectbb1in -> evalunperfectbb4in : D'=-1+B, E'=A, [ 0>=B ], cost: 1
16.11/10.96	
16.11/10.96	      7: evalunperfectbb1in -> evalunperfectbb4in : D'=-1+B, E'=A, [ B>=2 ], cost: 1
16.11/10.96	
16.11/10.96	      8: evalunperfectbb2in -> evalunperfectbb3in : [ 0>=1+C ], cost: 1
16.11/10.96	
16.11/10.96	      9: evalunperfectbb2in -> evalunperfectbb3in : [ C>=1 ], cost: 1
16.11/10.96	
16.11/10.96	     10: evalunperfectbb2in -> evalunperfectbb3in : [ C==0 ], cost: 1
16.11/10.96	
16.11/10.96	     11: evalunperfectbb3in -> evalunperfectstop : [], cost: 1
16.11/10.96	
16.11/10.96	     12: evalunperfectbb4in -> evalunperfectbb5in : [ E>=D ], cost: 1
16.11/10.96	
16.11/10.96	     13: evalunperfectbb4in -> evalunperfectbb6in : [ D>=1+E ], cost: 1
16.11/10.96	
16.11/10.96	     14: evalunperfectbb5in -> evalunperfectbb4in : E'=-D+E, [], cost: 1
16.11/10.96	
16.11/10.96	     15: evalunperfectbb6in -> evalunperfect9 : F'=C-D, [], cost: 1
16.11/10.96	
16.11/10.96	     16: evalunperfect9 -> evalunperfect10 : [], cost: 1
16.11/10.96	
16.11/10.96	     17: evalunperfect10 -> evalunperfect11 : G'=F, [ E==0 ], cost: 1
16.11/10.96	
16.11/10.96	     18: evalunperfect10 -> evalunperfect11 : G'=C, [ 0>=1+E ], cost: 1
16.11/10.96	
16.11/10.96	     19: evalunperfect10 -> evalunperfect11 : G'=C, [ E>=1 ], cost: 1
16.11/10.96	
16.11/10.96	     20: evalunperfect11 -> evalunperfect12 : [], cost: 1
16.11/10.96	
16.11/10.96	     21: evalunperfect12 -> evalunperfectbb1in : B'=D, C'=G, [], cost: 1
16.11/10.96
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