21.29/11.82 MAYBE 21.29/11.83 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 21.29/11.83 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 21.29/11.83 21.29/11.83 21.29/11.83 termination of the given Bare JBC problem could not be shown: 21.29/11.83 21.29/11.83 (0) Bare JBC problem 21.29/11.83 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 21.29/11.83 (2) JBC problem 21.29/11.83 (3) JBCToGraph [EQUIVALENT, 469 ms] 21.29/11.83 (4) JBCTerminationGraph 21.29/11.83 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 21.29/11.83 (6) JBCTerminationSCC 21.29/11.83 (7) SCCToIRSProof [SOUND, 44 ms] 21.29/11.83 (8) IRSwT 21.29/11.83 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 21.29/11.83 (10) IRSwT 21.29/11.83 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 35 ms] 21.29/11.83 (12) IRSwT 21.29/11.83 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 21.29/11.83 (14) IRSwT 21.29/11.83 (15) IRSwTChainingProof [EQUIVALENT, 0 ms] 21.29/11.83 (16) IRSwT 21.29/11.83 (17) IRSwTTerminationDigraphProof [EQUIVALENT, 25 ms] 21.29/11.83 (18) IRSwT 21.29/11.83 (19) IntTRSCompressionProof [EQUIVALENT, 0 ms] 21.29/11.83 (20) IRSwT 21.29/11.83 (21) TempFilterProof [SOUND, 1425 ms] 21.29/11.83 (22) IRSwT 21.29/11.83 (23) IRSwTTerminationDigraphProof [EQUIVALENT, 5 ms] 21.29/11.83 (24) IRSwT 21.29/11.83 (25) IntTRSCompressionProof [EQUIVALENT, 0 ms] 21.29/11.83 (26) IRSwT 21.29/11.83 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (0) 21.29/11.83 Obligation: 21.29/11.83 need to prove termination of the following program: 21.29/11.83 public class MinusUserDefined{ 21.29/11.83 public static boolean gt(int x, int y) { 21.29/11.83 21.29/11.83 while (x > 0 && y > 0) { 21.29/11.83 x--; 21.29/11.83 y--; 21.29/11.83 } 21.29/11.83 21.29/11.83 return x > 0; 21.29/11.83 } 21.29/11.83 21.29/11.83 21.29/11.83 public static void main(String[] args) { 21.29/11.83 Random.args = args; 21.29/11.83 int x = Random.random(); 21.29/11.83 int y = Random.random(); 21.29/11.83 int res = 0; 21.29/11.83 21.29/11.83 while (gt(x,y)) { 21.29/11.83 21.29/11.83 y++; 21.29/11.83 res++; 21.29/11.83 21.29/11.83 } 21.29/11.83 } 21.29/11.83 } 21.29/11.83 21.29/11.83 21.29/11.83 public class Random { 21.29/11.83 static String[] args; 21.29/11.83 static int index = 0; 21.29/11.83 21.29/11.83 public static int random() { 21.29/11.83 String string = args[index]; 21.29/11.83 index++; 21.29/11.83 return string.length(); 21.29/11.83 } 21.29/11.83 } 21.29/11.83 21.29/11.83 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (1) BareJBCToJBCProof (EQUIVALENT) 21.29/11.83 initialized classpath 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (2) 21.29/11.83 Obligation: 21.29/11.83 need to prove termination of the following program: 21.29/11.83 public class MinusUserDefined{ 21.29/11.83 public static boolean gt(int x, int y) { 21.29/11.83 21.29/11.83 while (x > 0 && y > 0) { 21.29/11.83 x--; 21.29/11.83 y--; 21.29/11.83 } 21.29/11.83 21.29/11.83 return x > 0; 21.29/11.83 } 21.29/11.83 21.29/11.83 21.29/11.83 public static void main(String[] args) { 21.29/11.83 Random.args = args; 21.29/11.83 int x = Random.random(); 21.29/11.83 int y = Random.random(); 21.29/11.83 int res = 0; 21.29/11.83 21.29/11.83 while (gt(x,y)) { 21.29/11.83 21.29/11.83 y++; 21.29/11.83 res++; 21.29/11.83 21.29/11.83 } 21.29/11.83 } 21.29/11.83 } 21.29/11.83 21.29/11.83 21.29/11.83 public class Random { 21.29/11.83 static String[] args; 21.29/11.83 static int index = 0; 21.29/11.83 21.29/11.83 public static int random() { 21.29/11.83 String string = args[index]; 21.29/11.83 index++; 21.29/11.83 return string.length(); 21.29/11.83 } 21.29/11.83 } 21.29/11.83 21.29/11.83 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (3) JBCToGraph (EQUIVALENT) 21.29/11.83 Constructed TerminationGraph. 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (4) 21.29/11.83 Obligation: 21.29/11.83 Termination Graph based on JBC Program: 21.29/11.83 MinusUserDefined.main([Ljava/lang/String;)V: Graph of 202 nodes with 1 SCC. 21.29/11.83 21.29/11.83 21.29/11.83 21.29/11.83 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (5) TerminationGraphToSCCProof (SOUND) 21.29/11.83 Splitted TerminationGraph to 1 SCCs. 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (6) 21.29/11.83 Obligation: 21.29/11.83 SCC of termination graph based on JBC Program. 21.29/11.83 SCC contains nodes from the following methods: MinusUserDefined.main([Ljava/lang/String;)V 21.29/11.83 SCC calls the following helper methods: 21.29/11.83 Performed SCC analyses: 21.29/11.83 *Used field analysis yielded the following read fields: 21.29/11.83 21.29/11.83 *Marker field analysis yielded the following relations that could be markers: 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (7) SCCToIRSProof (SOUND) 21.29/11.83 Transformed FIGraph SCCs to intTRSs. Log: 21.29/11.83 Generated rules. Obtained 26 IRulesP rules: 21.29/11.83 f3057_0_main_Load(EOS(STATIC_3057), i611, i612, i611) -> f3060_0_main_InvokeMethod(EOS(STATIC_3060), i611, i612, i611, i612) :|: TRUE 21.29/11.83 f3060_0_main_InvokeMethod(EOS(STATIC_3060), i611, i612, i611, i612) -> f3062_0_gt_Load(EOS(STATIC_3062), i611, i612, i611, i612) :|: TRUE 21.29/11.83 f3062_0_gt_Load(EOS(STATIC_3062), i611, i612, i611, i612) -> f3204_0_gt_Load(EOS(STATIC_3204), i611, i612, i611, i612) :|: TRUE 21.29/11.83 f3204_0_gt_Load(EOS(STATIC_3204), i651, i652, i649, i650) -> f3208_0_gt_LE(EOS(STATIC_3208), i651, i652, i649, i650, i649) :|: TRUE 21.29/11.83 f3208_0_gt_LE(EOS(STATIC_3208), i684, i652, i682, i650, i682) -> f3214_0_gt_LE(EOS(STATIC_3214), i684, i652, i682, i650, i682) :|: TRUE 21.29/11.83 f3214_0_gt_LE(EOS(STATIC_3214), i684, i652, i682, i650, i682) -> f3219_0_gt_Load(EOS(STATIC_3219), i684, i652, i682, i650) :|: i682 > 0 21.29/11.83 f3219_0_gt_Load(EOS(STATIC_3219), i684, i652, i682, i650) -> f3223_0_gt_LE(EOS(STATIC_3223), i684, i652, i682, i650, i650) :|: TRUE 21.29/11.83 f3223_0_gt_LE(EOS(STATIC_3223), i684, i652, i682, matching1, matching2) -> f3229_0_gt_LE(EOS(STATIC_3229), i684, i652, i682, 0, 0) :|: TRUE && matching1 = 0 && matching2 = 0 21.29/11.83 f3223_0_gt_LE(EOS(STATIC_3223), i684, i689, i682, i688, i688) -> f3231_0_gt_LE(EOS(STATIC_3231), i684, i689, i682, i688, i688) :|: TRUE 21.29/11.83 f3229_0_gt_LE(EOS(STATIC_3229), i684, i652, i682, matching1, matching2) -> f3236_0_gt_Load(EOS(STATIC_3236), i684, i652, i682) :|: 0 <= 0 && matching1 = 0 && matching2 = 0 21.29/11.83 f3236_0_gt_Load(EOS(STATIC_3236), i684, i652, i682) -> f3245_0_gt_LE(EOS(STATIC_3245), i684, i652, i682) :|: TRUE 21.29/11.83 f3245_0_gt_LE(EOS(STATIC_3245), i684, i652, i682) -> f3253_0_gt_ConstantStackPush(EOS(STATIC_3253), i684, i652) :|: i682 > 0 21.29/11.83 f3253_0_gt_ConstantStackPush(EOS(STATIC_3253), i684, i652) -> f3260_0_gt_JMP(EOS(STATIC_3260), i684, i652, 1) :|: TRUE 21.29/11.83 f3260_0_gt_JMP(EOS(STATIC_3260), i684, i652, matching1) -> f3430_0_gt_Return(EOS(STATIC_3430), i684, i652, 1) :|: TRUE && matching1 = 1 21.29/11.83 f3430_0_gt_Return(EOS(STATIC_3430), i684, i652, matching1) -> f3434_0_main_EQ(EOS(STATIC_3434), i684, i652, 1) :|: TRUE && matching1 = 1 21.29/11.83 f3434_0_main_EQ(EOS(STATIC_3434), i684, i652, matching1) -> f3437_0_main_Inc(EOS(STATIC_3437), i684, i652) :|: 1 > 0 && matching1 = 1 21.29/11.83 f3437_0_main_Inc(EOS(STATIC_3437), i684, i652) -> f3439_0_main_Inc(EOS(STATIC_3439), i684, i652 + 1) :|: TRUE 21.29/11.83 f3439_0_main_Inc(EOS(STATIC_3439), i684, i725) -> f3442_0_main_JMP(EOS(STATIC_3442), i684, i725) :|: TRUE 21.29/11.83 f3442_0_main_JMP(EOS(STATIC_3442), i684, i725) -> f3470_0_main_Load(EOS(STATIC_3470), i684, i725) :|: TRUE 21.29/11.83 f3470_0_main_Load(EOS(STATIC_3470), i684, i725) -> f3051_0_main_Load(EOS(STATIC_3051), i684, i725) :|: TRUE 21.29/11.83 f3051_0_main_Load(EOS(STATIC_3051), i611, i612) -> f3057_0_main_Load(EOS(STATIC_3057), i611, i612, i611) :|: TRUE 21.29/11.83 f3231_0_gt_LE(EOS(STATIC_3231), i684, i689, i682, i688, i688) -> f3238_0_gt_Inc(EOS(STATIC_3238), i684, i689, i682, i688) :|: i688 > 0 21.29/11.83 f3238_0_gt_Inc(EOS(STATIC_3238), i684, i689, i682, i688) -> f3248_0_gt_Inc(EOS(STATIC_3248), i684, i689, i682 + -1, i688) :|: TRUE 21.29/11.83 f3248_0_gt_Inc(EOS(STATIC_3248), i684, i689, i692, i688) -> f3254_0_gt_JMP(EOS(STATIC_3254), i684, i689, i692, i688 + -1) :|: TRUE 21.29/11.83 f3254_0_gt_JMP(EOS(STATIC_3254), i684, i689, i692, i693) -> f3425_0_gt_Load(EOS(STATIC_3425), i684, i689, i692, i693) :|: TRUE 21.29/11.83 f3425_0_gt_Load(EOS(STATIC_3425), i684, i689, i692, i693) -> f3204_0_gt_Load(EOS(STATIC_3204), i684, i689, i692, i693) :|: TRUE 21.29/11.83 Combined rules. Obtained 2 IRulesP rules: 21.29/11.83 f3223_0_gt_LE(EOS(STATIC_3223), i684:0, i652:0, i682:0, 0, 0) -> f3223_0_gt_LE(EOS(STATIC_3223), i684:0, i652:0 + 1, i684:0, i652:0 + 1, i652:0 + 1) :|: i684:0 > 0 && i682:0 > 0 21.29/11.83 f3223_0_gt_LE(EOS(STATIC_3223), i684:0, i689:0, i682:0, i688:0, i688:0) -> f3223_0_gt_LE(EOS(STATIC_3223), i684:0, i689:0, i682:0 - 1, i688:0 - 1, i688:0 - 1) :|: i682:0 > 1 && i688:0 > 0 21.29/11.83 Filtered constant ground arguments: 21.29/11.83 f3223_0_gt_LE(x1, x2, x3, x4, x5, x6) -> f3223_0_gt_LE(x2, x3, x4, x5, x6) 21.29/11.83 EOS(x1) -> EOS 21.29/11.83 Filtered duplicate arguments: 21.29/11.83 f3223_0_gt_LE(x1, x2, x3, x4, x5) -> f3223_0_gt_LE(x1, x2, x3, x5) 21.29/11.83 Finished conversion. Obtained 2 rules.P rules: 21.29/11.83 f3223_0_gt_LE(i684:0, i652:0, i682:0, cons_0) -> f3223_0_gt_LE(i684:0, i652:0 + 1, i684:0, i652:0 + 1) :|: i684:0 > 0 && i682:0 > 0 && cons_0 = 0 21.29/11.83 f3223_0_gt_LE(i684:0, i689:0, i682:0, i688:0) -> f3223_0_gt_LE(i684:0, i689:0, i682:0 - 1, i688:0 - 1) :|: i682:0 > 1 && i688:0 > 0 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (8) 21.29/11.83 Obligation: 21.29/11.83 Rules: 21.29/11.83 f3223_0_gt_LE(i684:0, i652:0, i682:0, cons_0) -> f3223_0_gt_LE(i684:0, i652:0 + 1, i684:0, i652:0 + 1) :|: i684:0 > 0 && i682:0 > 0 && cons_0 = 0 21.29/11.83 f3223_0_gt_LE(x, x1, x2, x3) -> f3223_0_gt_LE(x, x1, x2 - 1, x3 - 1) :|: x2 > 1 && x3 > 0 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (9) IRSFormatTransformerProof (EQUIVALENT) 21.29/11.83 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (10) 21.29/11.83 Obligation: 21.29/11.83 Rules: 21.29/11.83 f3223_0_gt_LE(i684:0, i652:0, i682:0, cons_0) -> f3223_0_gt_LE(i684:0, arith, i684:0, arith) :|: i684:0 > 0 && i682:0 > 0 && cons_0 = 0 && arith = i652:0 + 1 && arith = i652:0 + 1 21.29/11.83 f3223_0_gt_LE(x4, x5, x6, x7) -> f3223_0_gt_LE(x4, x5, x8, x9) :|: x6 > 1 && x7 > 0 && x8 = x6 - 1 && x9 = x7 - 1 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 21.29/11.83 Constructed termination digraph! 21.29/11.83 Nodes: 21.29/11.83 (1) f3223_0_gt_LE(i684:0, i652:0, i682:0, cons_0) -> f3223_0_gt_LE(i684:0, arith, i684:0, arith) :|: i684:0 > 0 && i682:0 > 0 && cons_0 = 0 && arith = i652:0 + 1 && arith = i652:0 + 1 21.29/11.83 (2) f3223_0_gt_LE(x4, x5, x6, x7) -> f3223_0_gt_LE(x4, x5, x8, x9) :|: x6 > 1 && x7 > 0 && x8 = x6 - 1 && x9 = x7 - 1 21.29/11.83 21.29/11.83 Arcs: 21.29/11.83 (1) -> (1), (2) 21.29/11.83 (2) -> (1), (2) 21.29/11.83 21.29/11.83 This digraph is fully evaluated! 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (12) 21.29/11.83 Obligation: 21.29/11.83 21.29/11.83 Termination digraph: 21.29/11.83 Nodes: 21.29/11.83 (1) f3223_0_gt_LE(i684:0, i652:0, i682:0, cons_0) -> f3223_0_gt_LE(i684:0, arith, i684:0, arith) :|: i684:0 > 0 && i682:0 > 0 && cons_0 = 0 && arith = i652:0 + 1 && arith = i652:0 + 1 21.29/11.83 (2) f3223_0_gt_LE(x4, x5, x6, x7) -> f3223_0_gt_LE(x4, x5, x8, x9) :|: x6 > 1 && x7 > 0 && x8 = x6 - 1 && x9 = x7 - 1 21.29/11.83 21.29/11.83 Arcs: 21.29/11.83 (1) -> (1), (2) 21.29/11.83 (2) -> (1), (2) 21.29/11.83 21.29/11.83 This digraph is fully evaluated! 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (13) IntTRSCompressionProof (EQUIVALENT) 21.29/11.83 Compressed rules. 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (14) 21.29/11.83 Obligation: 21.29/11.83 Rules: 21.29/11.83 f3223_0_gt_LE(i684:0:0, i652:0:0, i682:0:0, cons_0) -> f3223_0_gt_LE(i684:0:0, i652:0:0 + 1, i684:0:0, i652:0:0 + 1) :|: i684:0:0 > 0 && i682:0:0 > 0 && cons_0 = 0 21.29/11.83 f3223_0_gt_LE(x4:0, x5:0, x6:0, x7:0) -> f3223_0_gt_LE(x4:0, x5:0, x6:0 - 1, x7:0 - 1) :|: x6:0 > 1 && x7:0 > 0 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (15) IRSwTChainingProof (EQUIVALENT) 21.29/11.83 Chaining! 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (16) 21.29/11.83 Obligation: 21.29/11.83 Rules: 21.29/11.83 f3223_0_gt_LE(x, x1, x2, x3) -> f3223_0_gt_LE(x, x1 + 2, x, x1 + 2) :|: TRUE && x >= 1 && x2 >= 1 && x1 = -1 && x3 = 0 21.29/11.83 f3223_0_gt_LE(x4:0, x5:0, x6:0, x7:0) -> f3223_0_gt_LE(x4:0, x5:0, x6:0 - 1, x7:0 - 1) :|: x6:0 > 1 && x7:0 > 0 21.29/11.83 f3223_0_gt_LE(x8, x9, x10, x11) -> f3223_0_gt_LE(x8, x9 + 1, x8 + -1, x9) :|: TRUE && x10 >= 1 && x8 >= 2 && x9 >= 0 && x11 = 0 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (17) IRSwTTerminationDigraphProof (EQUIVALENT) 21.29/11.83 Constructed termination digraph! 21.29/11.83 Nodes: 21.29/11.83 (1) f3223_0_gt_LE(x, x1, x2, x3) -> f3223_0_gt_LE(x, x1 + 2, x, x1 + 2) :|: TRUE && x >= 1 && x2 >= 1 && x1 = -1 && x3 = 0 21.29/11.83 (2) f3223_0_gt_LE(x4:0, x5:0, x6:0, x7:0) -> f3223_0_gt_LE(x4:0, x5:0, x6:0 - 1, x7:0 - 1) :|: x6:0 > 1 && x7:0 > 0 21.29/11.83 (3) f3223_0_gt_LE(x8, x9, x10, x11) -> f3223_0_gt_LE(x8, x9 + 1, x8 + -1, x9) :|: TRUE && x10 >= 1 && x8 >= 2 && x9 >= 0 && x11 = 0 21.29/11.83 21.29/11.83 Arcs: 21.29/11.83 (1) -> (2) 21.29/11.83 (2) -> (1), (2), (3) 21.29/11.83 (3) -> (2), (3) 21.29/11.83 21.29/11.83 This digraph is fully evaluated! 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (18) 21.29/11.83 Obligation: 21.29/11.83 21.29/11.83 Termination digraph: 21.29/11.83 Nodes: 21.29/11.83 (1) f3223_0_gt_LE(x, x1, x2, x3) -> f3223_0_gt_LE(x, x1 + 2, x, x1 + 2) :|: TRUE && x >= 1 && x2 >= 1 && x1 = -1 && x3 = 0 21.29/11.83 (2) f3223_0_gt_LE(x4:0, x5:0, x6:0, x7:0) -> f3223_0_gt_LE(x4:0, x5:0, x6:0 - 1, x7:0 - 1) :|: x6:0 > 1 && x7:0 > 0 21.29/11.83 (3) f3223_0_gt_LE(x8, x9, x10, x11) -> f3223_0_gt_LE(x8, x9 + 1, x8 + -1, x9) :|: TRUE && x10 >= 1 && x8 >= 2 && x9 >= 0 && x11 = 0 21.29/11.83 21.29/11.83 Arcs: 21.29/11.83 (1) -> (2) 21.29/11.83 (2) -> (1), (2), (3) 21.29/11.83 (3) -> (2), (3) 21.29/11.83 21.29/11.83 This digraph is fully evaluated! 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (19) IntTRSCompressionProof (EQUIVALENT) 21.29/11.83 Compressed rules. 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (20) 21.29/11.83 Obligation: 21.29/11.83 Rules: 21.29/11.83 f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0, x7:0:0) -> f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0 - 1, x7:0:0 - 1) :|: x6:0:0 > 1 && x7:0:0 > 0 21.29/11.83 f3223_0_gt_LE(x8:0, x9:0, x10:0, cons_0) -> f3223_0_gt_LE(x8:0, x9:0 + 1, x8:0 - 1, x9:0) :|: x8:0 > 1 && x10:0 > 0 && x9:0 > -1 && cons_0 = 0 21.29/11.83 f3223_0_gt_LE(x, x1, x2, x3) -> f3223_0_gt_LE(x, 1, x, 1) :|: x2 > 0 && x > 0 && x1 = -1 && x3 = 0 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (21) TempFilterProof (SOUND) 21.29/11.83 Used the following sort dictionary for filtering: 21.29/11.83 f3223_0_gt_LE(VARIABLE, VARIABLE, INTEGER, VARIABLE) 21.29/11.83 Replaced non-predefined constructor symbols by 0.The following proof was generated: 21.29/11.83 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 21.29/11.83 21.29/11.83 21.29/11.83 Termination of the given IntTRS could not be shown: 21.29/11.83 21.29/11.83 21.29/11.83 21.29/11.83 - IntTRS 21.29/11.83 - PolynomialOrderProcessor 21.29/11.83 21.29/11.83 Rules: 21.29/11.83 f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0, x7:0:0) -> f3223_0_gt_LE(x4:0:0, x5:0:0, c, c1) :|: c1 = x7:0:0 - 1 && c = x6:0:0 - 1 && (x6:0:0 > 1 && x7:0:0 > 0) 21.29/11.83 f3223_0_gt_LE(x8:0, x9:0, x10:0, c2) -> f3223_0_gt_LE(x8:0, c3, c4, x9:0) :|: c4 = x8:0 - 1 && (c3 = x9:0 + 1 && c2 = 0) && (x8:0 > 1 && x10:0 > 0 && x9:0 > -1 && cons_0 = 0) 21.29/11.83 f3223_0_gt_LE(x, c5, x2, c6) -> f3223_0_gt_LE(x, c7, x, c8) :|: c8 = 1 && (c7 = 1 && (c6 = 0 && c5 = -1)) && (x2 > 0 && x > 0 && x1 = -1 && x3 = 0) 21.29/11.83 21.29/11.83 Found the following polynomial interpretation: 21.29/11.83 [f3223_0_gt_LE(x, x1, x2, x3)] = -3 + x - 2*x1 21.29/11.83 21.29/11.83 The following rules are decreasing: 21.29/11.83 f3223_0_gt_LE(x8:0, x9:0, x10:0, c2) -> f3223_0_gt_LE(x8:0, c3, c4, x9:0) :|: c4 = x8:0 - 1 && (c3 = x9:0 + 1 && c2 = 0) && (x8:0 > 1 && x10:0 > 0 && x9:0 > -1 && cons_0 = 0) 21.29/11.83 f3223_0_gt_LE(x, c5, x2, c6) -> f3223_0_gt_LE(x, c7, x, c8) :|: c8 = 1 && (c7 = 1 && (c6 = 0 && c5 = -1)) && (x2 > 0 && x > 0 && x1 = -1 && x3 = 0) 21.29/11.83 The following rules are bounded: 21.29/11.83 f3223_0_gt_LE(x, c5, x2, c6) -> f3223_0_gt_LE(x, c7, x, c8) :|: c8 = 1 && (c7 = 1 && (c6 = 0 && c5 = -1)) && (x2 > 0 && x > 0 && x1 = -1 && x3 = 0) 21.29/11.83 21.29/11.83 21.29/11.83 - IntTRS 21.29/11.83 - PolynomialOrderProcessor 21.29/11.83 - IntTRS 21.29/11.83 21.29/11.83 Rules: 21.29/11.83 f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0, x7:0:0) -> f3223_0_gt_LE(x4:0:0, x5:0:0, c, c1) :|: c1 = x7:0:0 - 1 && c = x6:0:0 - 1 && (x6:0:0 > 1 && x7:0:0 > 0) 21.29/11.83 f3223_0_gt_LE(x8:0, x9:0, x10:0, c2) -> f3223_0_gt_LE(x8:0, c3, c4, x9:0) :|: c4 = x8:0 - 1 && (c3 = x9:0 + 1 && c2 = 0) && (x8:0 > 1 && x10:0 > 0 && x9:0 > -1 && cons_0 = 0) 21.29/11.83 21.29/11.83 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (22) 21.29/11.83 Obligation: 21.29/11.83 Rules: 21.29/11.83 f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0, x7:0:0) -> f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0 - 1, x7:0:0 - 1) :|: x6:0:0 > 1 && x7:0:0 > 0 21.29/11.83 f3223_0_gt_LE(x8:0, x9:0, x10:0, cons_0) -> f3223_0_gt_LE(x8:0, x9:0 + 1, x8:0 - 1, x9:0) :|: x8:0 > 1 && x10:0 > 0 && x9:0 > -1 && cons_0 = 0 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (23) IRSwTTerminationDigraphProof (EQUIVALENT) 21.29/11.83 Constructed termination digraph! 21.29/11.83 Nodes: 21.29/11.83 (1) f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0, x7:0:0) -> f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0 - 1, x7:0:0 - 1) :|: x6:0:0 > 1 && x7:0:0 > 0 21.29/11.83 (2) f3223_0_gt_LE(x8:0, x9:0, x10:0, cons_0) -> f3223_0_gt_LE(x8:0, x9:0 + 1, x8:0 - 1, x9:0) :|: x8:0 > 1 && x10:0 > 0 && x9:0 > -1 && cons_0 = 0 21.29/11.83 21.29/11.83 Arcs: 21.29/11.83 (1) -> (1), (2) 21.29/11.83 (2) -> (1), (2) 21.29/11.83 21.29/11.83 This digraph is fully evaluated! 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (24) 21.29/11.83 Obligation: 21.29/11.83 21.29/11.83 Termination digraph: 21.29/11.83 Nodes: 21.29/11.83 (1) f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0, x7:0:0) -> f3223_0_gt_LE(x4:0:0, x5:0:0, x6:0:0 - 1, x7:0:0 - 1) :|: x6:0:0 > 1 && x7:0:0 > 0 21.29/11.83 (2) f3223_0_gt_LE(x8:0, x9:0, x10:0, cons_0) -> f3223_0_gt_LE(x8:0, x9:0 + 1, x8:0 - 1, x9:0) :|: x8:0 > 1 && x10:0 > 0 && x9:0 > -1 && cons_0 = 0 21.29/11.83 21.29/11.83 Arcs: 21.29/11.83 (1) -> (1), (2) 21.29/11.83 (2) -> (1), (2) 21.29/11.83 21.29/11.83 This digraph is fully evaluated! 21.29/11.83 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (25) IntTRSCompressionProof (EQUIVALENT) 21.29/11.83 Compressed rules. 21.29/11.83 ---------------------------------------- 21.29/11.83 21.29/11.83 (26) 21.29/11.83 Obligation: 21.29/11.83 Rules: 21.29/11.83 f3223_0_gt_LE(x4:0:0:0, x5:0:0:0, x6:0:0:0, x7:0:0:0) -> f3223_0_gt_LE(x4:0:0:0, x5:0:0:0, x6:0:0:0 - 1, x7:0:0:0 - 1) :|: x6:0:0:0 > 1 && x7:0:0:0 > 0 21.29/11.83 f3223_0_gt_LE(x8:0:0, x9:0:0, x10:0:0, cons_0) -> f3223_0_gt_LE(x8:0:0, x9:0:0 + 1, x8:0:0 - 1, x9:0:0) :|: x8:0:0 > 1 && x10:0:0 > 0 && x9:0:0 > -1 && cons_0 = 0 21.36/11.86 EOF