/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.jar /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty termination of the given Bare JBC problem could not be shown: (0) Bare JBC problem (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 275 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) JBCTerminationSCC (7) SCCToIRSProof [SOUND, 61 ms] (8) IRSwT (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (10) IRSwT (11) IRSwTTerminationDigraphProof [EQUIVALENT, 38 ms] (12) IRSwT (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] (14) IRSwT (15) IRSwTChainingProof [EQUIVALENT, 0 ms] (16) IRSwT (17) IRSwTTerminationDigraphProof [EQUIVALENT, 11 ms] (18) IRSwT (19) IntTRSCompressionProof [EQUIVALENT, 0 ms] (20) IRSwT (21) IRSwTChainingProof [EQUIVALENT, 0 ms] (22) IRSwT (23) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (24) IRSwT (25) IntTRSCompressionProof [EQUIVALENT, 0 ms] (26) IRSwT (27) IRSwTChainingProof [EQUIVALENT, 0 ms] (28) IRSwT (29) IRSwTTerminationDigraphProof [EQUIVALENT, 15 ms] (30) IRSwT (31) IntTRSCompressionProof [EQUIVALENT, 0 ms] (32) IRSwT (33) TempFilterProof [SOUND, 167 ms] (34) IRSwT (35) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (36) IRSwT (37) IntTRSCompressionProof [EQUIVALENT, 0 ms] (38) IRSwT ---------------------------------------- (0) Obligation: need to prove termination of the following program: /** * All lasso-shaped runs of this program are terminating. */ public class MultiLasso { public static void main(String[] args) { int x = args[0].length() - args[1].length(); int y; while (x > 0) { x++; y = x; while (y > 0) { y--; } } } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: /** * All lasso-shaped runs of this program are terminating. */ public class MultiLasso { public static void main(String[] args) { int x = args[0].length() - args[1].length(); int y; while (x > 0) { x++; y = x; while (y > 0) { y--; } } } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: MultiLasso.main([Ljava/lang/String;)V: Graph of 134 nodes with 1 SCC. ---------------------------------------- (5) TerminationGraphToSCCProof (SOUND) Splitted TerminationGraph to 1 SCCs. ---------------------------------------- (6) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: MultiLasso.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (7) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 17 IRulesP rules: f166_0_main_LE(EOS(STATIC_166), i38, i38) -> f179_0_main_LE(EOS(STATIC_179), i38, i38) :|: TRUE f179_0_main_LE(EOS(STATIC_179), i38, i38) -> f187_0_main_Inc(EOS(STATIC_187), i38) :|: i38 > 0 f187_0_main_Inc(EOS(STATIC_187), i38) -> f204_0_main_Load(EOS(STATIC_204), i38 + 1) :|: TRUE f204_0_main_Load(EOS(STATIC_204), i40) -> f209_0_main_Store(EOS(STATIC_209), i40, i40) :|: TRUE f209_0_main_Store(EOS(STATIC_209), i40, i40) -> f217_0_main_Load(EOS(STATIC_217), i40, i40) :|: TRUE f217_0_main_Load(EOS(STATIC_217), i40, i40) -> f817_0_main_Load(EOS(STATIC_817), i40, i40) :|: TRUE f817_0_main_Load(EOS(STATIC_817), i40, i62) -> f969_0_main_Load(EOS(STATIC_969), i40, i62) :|: TRUE f969_0_main_Load(EOS(STATIC_969), i40, i195) -> f979_0_main_LE(EOS(STATIC_979), i40, i195, i195) :|: TRUE f979_0_main_LE(EOS(STATIC_979), i40, matching1, matching2) -> f986_0_main_LE(EOS(STATIC_986), i40, 0, 0) :|: TRUE && matching1 = 0 && matching2 = 0 f979_0_main_LE(EOS(STATIC_979), i40, i222, i222) -> f987_0_main_LE(EOS(STATIC_987), i40, i222, i222) :|: TRUE f986_0_main_LE(EOS(STATIC_986), i40, matching1, matching2) -> f1025_0_main_Load(EOS(STATIC_1025), i40) :|: 0 <= 0 && matching1 = 0 && matching2 = 0 f1025_0_main_Load(EOS(STATIC_1025), i40) -> f153_0_main_Load(EOS(STATIC_153), i40) :|: TRUE f153_0_main_Load(EOS(STATIC_153), i34) -> f166_0_main_LE(EOS(STATIC_166), i34, i34) :|: TRUE f987_0_main_LE(EOS(STATIC_987), i40, i222, i222) -> f1028_0_main_Inc(EOS(STATIC_1028), i40, i222) :|: i222 > 0 f1028_0_main_Inc(EOS(STATIC_1028), i40, i222) -> f1031_0_main_JMP(EOS(STATIC_1031), i40, i222 + -1) :|: TRUE f1031_0_main_JMP(EOS(STATIC_1031), i40, i239) -> f1051_0_main_Load(EOS(STATIC_1051), i40, i239) :|: TRUE f1051_0_main_Load(EOS(STATIC_1051), i40, i239) -> f969_0_main_Load(EOS(STATIC_969), i40, i239) :|: TRUE Combined rules. Obtained 2 IRulesP rules: f979_0_main_LE(EOS(STATIC_979), i40:0, i222:0, i222:0) -> f979_0_main_LE(EOS(STATIC_979), i40:0, i222:0 - 1, i222:0 - 1) :|: i222:0 > 0 f979_0_main_LE(EOS(STATIC_979), i40:0, 0, 0) -> f979_0_main_LE(EOS(STATIC_979), i40:0 + 1, i40:0 + 1, i40:0 + 1) :|: i40:0 > 0 Filtered constant ground arguments: f979_0_main_LE(x1, x2, x3, x4) -> f979_0_main_LE(x2, x3, x4) EOS(x1) -> EOS Filtered duplicate arguments: f979_0_main_LE(x1, x2, x3) -> f979_0_main_LE(x1, x3) Finished conversion. Obtained 2 rules.P rules: f979_0_main_LE(i40:0, i222:0) -> f979_0_main_LE(i40:0, i222:0 - 1) :|: i222:0 > 0 f979_0_main_LE(i40:0, cons_0) -> f979_0_main_LE(i40:0 + 1, i40:0 + 1) :|: i40:0 > 0 && cons_0 = 0 ---------------------------------------- (8) Obligation: Rules: f979_0_main_LE(i40:0, i222:0) -> f979_0_main_LE(i40:0, i222:0 - 1) :|: i222:0 > 0 f979_0_main_LE(x, x1) -> f979_0_main_LE(x + 1, x + 1) :|: x > 0 && x1 = 0 ---------------------------------------- (9) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (10) Obligation: Rules: f979_0_main_LE(i40:0, i222:0) -> f979_0_main_LE(i40:0, arith) :|: i222:0 > 0 && arith = i222:0 - 1 f979_0_main_LE(x2, x3) -> f979_0_main_LE(x4, x4) :|: x2 > 0 && x3 = 0 && x4 = x2 + 1 && x4 = x2 + 1 ---------------------------------------- (11) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f979_0_main_LE(i40:0, i222:0) -> f979_0_main_LE(i40:0, arith) :|: i222:0 > 0 && arith = i222:0 - 1 (2) f979_0_main_LE(x2, x3) -> f979_0_main_LE(x4, x4) :|: x2 > 0 && x3 = 0 && x4 = x2 + 1 && x4 = x2 + 1 Arcs: (1) -> (1), (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (12) Obligation: Termination digraph: Nodes: (1) f979_0_main_LE(i40:0, i222:0) -> f979_0_main_LE(i40:0, arith) :|: i222:0 > 0 && arith = i222:0 - 1 (2) f979_0_main_LE(x2, x3) -> f979_0_main_LE(x4, x4) :|: x2 > 0 && x3 = 0 && x4 = x2 + 1 && x4 = x2 + 1 Arcs: (1) -> (1), (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (13) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (14) Obligation: Rules: f979_0_main_LE(x2:0, cons_0) -> f979_0_main_LE(x2:0 + 1, x2:0 + 1) :|: x2:0 > 0 && cons_0 = 0 f979_0_main_LE(i40:0:0, i222:0:0) -> f979_0_main_LE(i40:0:0, i222:0:0 - 1) :|: i222:0:0 > 0 ---------------------------------------- (15) IRSwTChainingProof (EQUIVALENT) Chaining! ---------------------------------------- (16) Obligation: Rules: f979_0_main_LE(i40:0:0, i222:0:0) -> f979_0_main_LE(i40:0:0, i222:0:0 - 1) :|: i222:0:0 > 0 f979_0_main_LE(x4, x5) -> f979_0_main_LE(x4 + 1, x4) :|: TRUE && x4 >= 1 && x5 = 0 ---------------------------------------- (17) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f979_0_main_LE(i40:0:0, i222:0:0) -> f979_0_main_LE(i40:0:0, i222:0:0 - 1) :|: i222:0:0 > 0 (2) f979_0_main_LE(x4, x5) -> f979_0_main_LE(x4 + 1, x4) :|: TRUE && x4 >= 1 && x5 = 0 Arcs: (1) -> (1), (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (18) Obligation: Termination digraph: Nodes: (1) f979_0_main_LE(i40:0:0, i222:0:0) -> f979_0_main_LE(i40:0:0, i222:0:0 - 1) :|: i222:0:0 > 0 (2) f979_0_main_LE(x4, x5) -> f979_0_main_LE(x4 + 1, x4) :|: TRUE && x4 >= 1 && x5 = 0 Arcs: (1) -> (1), (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (19) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (20) Obligation: Rules: f979_0_main_LE(x4:0, cons_0) -> f979_0_main_LE(x4:0 + 1, x4:0) :|: x4:0 > 0 && cons_0 = 0 f979_0_main_LE(i40:0:0:0, i222:0:0:0) -> f979_0_main_LE(i40:0:0:0, i222:0:0:0 - 1) :|: i222:0:0:0 > 0 ---------------------------------------- (21) IRSwTChainingProof (EQUIVALENT) Chaining! ---------------------------------------- (22) Obligation: Rules: f979_0_main_LE(i40:0:0:0, i222:0:0:0) -> f979_0_main_LE(i40:0:0:0, i222:0:0:0 - 1) :|: i222:0:0:0 > 0 f979_0_main_LE(x4, x5) -> f979_0_main_LE(x4 + 1, x4 + -1) :|: TRUE && x4 >= 1 && x5 = 0 ---------------------------------------- (23) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f979_0_main_LE(i40:0:0:0, i222:0:0:0) -> f979_0_main_LE(i40:0:0:0, i222:0:0:0 - 1) :|: i222:0:0:0 > 0 (2) f979_0_main_LE(x4, x5) -> f979_0_main_LE(x4 + 1, x4 + -1) :|: TRUE && x4 >= 1 && x5 = 0 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (24) Obligation: Termination digraph: Nodes: (1) f979_0_main_LE(i40:0:0:0, i222:0:0:0) -> f979_0_main_LE(i40:0:0:0, i222:0:0:0 - 1) :|: i222:0:0:0 > 0 (2) f979_0_main_LE(x4, x5) -> f979_0_main_LE(x4 + 1, x4 + -1) :|: TRUE && x4 >= 1 && x5 = 0 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (25) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (26) Obligation: Rules: f979_0_main_LE(x4:0, cons_0) -> f979_0_main_LE(x4:0 + 1, x4:0 - 1) :|: x4:0 > 0 && cons_0 = 0 f979_0_main_LE(i40:0:0:0:0, i222:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0, i222:0:0:0:0 - 1) :|: i222:0:0:0:0 > 0 ---------------------------------------- (27) IRSwTChainingProof (EQUIVALENT) Chaining! ---------------------------------------- (28) Obligation: Rules: f979_0_main_LE(x, x1) -> f979_0_main_LE(x + 2, x) :|: TRUE && x = 1 && x1 = 0 f979_0_main_LE(i40:0:0:0:0, i222:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0, i222:0:0:0:0 - 1) :|: i222:0:0:0:0 > 0 f979_0_main_LE(x4, x5) -> f979_0_main_LE(x4 + 1, x4 + -2) :|: TRUE && x4 >= 2 && x5 = 0 ---------------------------------------- (29) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f979_0_main_LE(x, x1) -> f979_0_main_LE(x + 2, x) :|: TRUE && x = 1 && x1 = 0 (2) f979_0_main_LE(i40:0:0:0:0, i222:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0, i222:0:0:0:0 - 1) :|: i222:0:0:0:0 > 0 (3) f979_0_main_LE(x4, x5) -> f979_0_main_LE(x4 + 1, x4 + -2) :|: TRUE && x4 >= 2 && x5 = 0 Arcs: (1) -> (2) (2) -> (1), (2), (3) (3) -> (2), (3) This digraph is fully evaluated! ---------------------------------------- (30) Obligation: Termination digraph: Nodes: (1) f979_0_main_LE(x, x1) -> f979_0_main_LE(x + 2, x) :|: TRUE && x = 1 && x1 = 0 (2) f979_0_main_LE(i40:0:0:0:0, i222:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0, i222:0:0:0:0 - 1) :|: i222:0:0:0:0 > 0 (3) f979_0_main_LE(x4, x5) -> f979_0_main_LE(x4 + 1, x4 + -2) :|: TRUE && x4 >= 2 && x5 = 0 Arcs: (1) -> (2) (2) -> (1), (2), (3) (3) -> (2), (3) This digraph is fully evaluated! ---------------------------------------- (31) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (32) Obligation: Rules: f979_0_main_LE(x4:0, cons_0) -> f979_0_main_LE(x4:0 + 1, x4:0 - 2) :|: x4:0 > 1 && cons_0 = 0 f979_0_main_LE(x, x1) -> f979_0_main_LE(3, 1) :|: TRUE && x = 1 && x1 = 0 f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0 - 1) :|: i222:0:0:0:0:0 > 0 ---------------------------------------- (33) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f979_0_main_LE(VARIABLE, VARIABLE) Replaced non-predefined constructor symbols by 0.The following proof was generated: # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination of the given IntTRS could not be shown: - IntTRS - RankingReductionPairProof Rules: f979_0_main_LE(x4:0, c) -> f979_0_main_LE(c1, c2) :|: c2 = x4:0 - 2 && (c1 = x4:0 + 1 && c = 0) && (x4:0 > 1 && cons_0 = 0) f979_0_main_LE(c3, c4) -> f979_0_main_LE(c5, c6) :|: c6 = 1 && (c5 = 3 && (c4 = 0 && c3 = 1)) && (TRUE && x = 1 && x1 = 0) f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0:0, c7) :|: c7 = i222:0:0:0:0:0 - 1 && i222:0:0:0:0:0 > 0 Interpretation: [ f979_0_main_LE ] = -1*f979_0_main_LE_1 The following rules are decreasing: f979_0_main_LE(x4:0, c) -> f979_0_main_LE(c1, c2) :|: c2 = x4:0 - 2 && (c1 = x4:0 + 1 && c = 0) && (x4:0 > 1 && cons_0 = 0) f979_0_main_LE(c3, c4) -> f979_0_main_LE(c5, c6) :|: c6 = 1 && (c5 = 3 && (c4 = 0 && c3 = 1)) && (TRUE && x = 1 && x1 = 0) The following rules are bounded: f979_0_main_LE(c3, c4) -> f979_0_main_LE(c5, c6) :|: c6 = 1 && (c5 = 3 && (c4 = 0 && c3 = 1)) && (TRUE && x = 1 && x1 = 0) - IntTRS - RankingReductionPairProof - IntTRS Rules: f979_0_main_LE(x4:0, c) -> f979_0_main_LE(c1, c2) :|: c2 = x4:0 - 2 && (c1 = x4:0 + 1 && c = 0) && (x4:0 > 1 && cons_0 = 0) f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0:0, c7) :|: c7 = i222:0:0:0:0:0 - 1 && i222:0:0:0:0:0 > 0 ---------------------------------------- (34) Obligation: Rules: f979_0_main_LE(x4:0, cons_0) -> f979_0_main_LE(x4:0 + 1, x4:0 - 2) :|: x4:0 > 1 && cons_0 = 0 f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0 - 1) :|: i222:0:0:0:0:0 > 0 ---------------------------------------- (35) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f979_0_main_LE(x4:0, cons_0) -> f979_0_main_LE(x4:0 + 1, x4:0 - 2) :|: x4:0 > 1 && cons_0 = 0 (2) f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0 - 1) :|: i222:0:0:0:0:0 > 0 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (36) Obligation: Termination digraph: Nodes: (1) f979_0_main_LE(x4:0, cons_0) -> f979_0_main_LE(x4:0 + 1, x4:0 - 2) :|: x4:0 > 1 && cons_0 = 0 (2) f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0:0, i222:0:0:0:0:0 - 1) :|: i222:0:0:0:0:0 > 0 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (37) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (38) Obligation: Rules: f979_0_main_LE(x4:0:0, cons_0) -> f979_0_main_LE(x4:0:0 + 1, x4:0:0 - 2) :|: x4:0:0 > 1 && cons_0 = 0 f979_0_main_LE(i40:0:0:0:0:0:0, i222:0:0:0:0:0:0) -> f979_0_main_LE(i40:0:0:0:0:0:0, i222:0:0:0:0:0:0 - 1) :|: i222:0:0:0:0:0:0 > 0