NO ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: __init 0: f1_0_main_Load -> f213_0_increase_LE : arg1'=arg1P_1, arg2'=arg2P_1, arg3'=arg3P_1, [ arg1P_1>-1 && arg2>1 && arg2P_1>-1 && arg1>0 && arg1P_1+arg2P_1==arg3P_1 ], cost: 1 1: f213_0_increase_LE -> f213_0_increase_LE\' : arg1'=arg1P_2, arg2'=arg2P_2, arg3'=arg3P_2, [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && arg1==arg1P_2 && arg2==arg2P_2 && arg3==arg3P_2 ], cost: 1 2: f213_0_increase_LE -> f213_0_increase_LE\' : arg1'=arg1P_3, arg2'=arg2P_3, arg3'=arg3P_3, [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 && arg1==arg1P_3 && arg2==arg2P_3 && arg3==arg3P_3 ], cost: 1 4: f213_0_increase_LE -> f213_0_increase_LE\' : arg1'=arg1P_5, arg2'=arg2P_5, arg3'=arg3P_5, [ arg1>-2 && arg2-2*x25_1==0 && arg3>0 && arg1==arg1P_5 && arg2==arg2P_5 && arg3==arg3P_5 ], cost: 1 3: f213_0_increase_LE\' -> f213_0_increase_LE : arg1'=arg1P_4, arg2'=arg2P_4, arg3'=arg3P_4, [ arg2-2*x21_1>0 && arg1>-2 && arg2-2*x21_1<2 && arg3>0 && 1+arg1==arg1P_4 && arg2==arg2P_4 && 1+arg2+arg1==arg3P_4 ], cost: 1 5: f213_0_increase_LE\' -> f213_0_increase_LE : arg1'=arg1P_6, arg2'=arg2P_6, arg3'=arg3P_6, [ arg1>-2 && arg3>0 && arg2-2*x29_1==0 && arg2-2*x29_1<2 && arg2-2*x29_1>=0 && 1+arg1==arg1P_6 && -2+arg2==arg2P_6 && -1+arg2+arg1==arg3P_6 ], cost: 1 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, arg3'=arg3P_7, [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, arg3'=arg3P_7, [], cost: 1 Simplified all rules, resulting in: Start location: __init 0: f1_0_main_Load -> f213_0_increase_LE : arg1'=arg1P_1, arg2'=arg2P_1, arg3'=arg1P_1+arg2P_1, [ arg1P_1>-1 && arg2>1 && arg2P_1>-1 && arg1>0 ], cost: 1 1: f213_0_increase_LE -> f213_0_increase_LE\' : [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 ], cost: 1 2: f213_0_increase_LE -> f213_0_increase_LE\' : [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 ], cost: 1 4: f213_0_increase_LE -> f213_0_increase_LE\' : [ arg1>-2 && arg2-2*x25_1==0 && arg3>0 ], cost: 1 3: f213_0_increase_LE\' -> f213_0_increase_LE : arg1'=1+arg1, arg3'=1+arg2+arg1, [ 1-arg2+2*x21_1==0 && arg1>-2 && arg3>0 ], cost: 1 5: f213_0_increase_LE\' -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg3>0 && arg2-2*x29_1==0 ], cost: 1 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, arg3'=arg3P_7, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: __init 1: f213_0_increase_LE -> f213_0_increase_LE\' : [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 ], cost: 1 2: f213_0_increase_LE -> f213_0_increase_LE\' : [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 ], cost: 1 4: f213_0_increase_LE -> f213_0_increase_LE\' : [ arg1>-2 && arg2-2*x25_1==0 && arg3>0 ], cost: 1 3: f213_0_increase_LE\' -> f213_0_increase_LE : arg1'=1+arg1, arg3'=1+arg2+arg1, [ 1-arg2+2*x21_1==0 && arg1>-2 && arg3>0 ], cost: 1 5: f213_0_increase_LE\' -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg3>0 && arg2-2*x29_1==0 ], cost: 1 7: __init -> f213_0_increase_LE : arg1'=arg1P_1, arg2'=arg2P_1, arg3'=arg1P_1+arg2P_1, [ arg1P_1>-1 && arg2P_7>1 && arg2P_1>-1 && arg1P_7>0 ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: __init 8: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg3'=1+arg2+arg1, [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && 1-arg2+2*x21_1==0 ], cost: 2 9: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && arg2-2*x29_1==0 ], cost: 2 10: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg3'=1+arg2+arg1, [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 && 1-arg2+2*x21_1==0 ], cost: 2 11: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 && arg2-2*x29_1==0 ], cost: 2 12: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg2-2*x25_1==0 && arg3>0 && arg2-2*x29_1==0 ], cost: 2 7: __init -> f213_0_increase_LE : arg1'=arg1P_1, arg2'=arg2P_1, arg3'=arg1P_1+arg2P_1, [ arg1P_1>-1 && arg2P_7>1 && arg2P_1>-1 && arg1P_7>0 ], cost: 2 Accelerating simple loops of location 1. Accelerating the following rules: 8: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg3'=1+arg2+arg1, [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && 1-arg2+2*x21_1==0 ], cost: 2 9: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && arg2-2*x29_1==0 ], cost: 2 10: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg3'=1+arg2+arg1, [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 && 1-arg2+2*x21_1==0 ], cost: 2 11: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 && arg2-2*x29_1==0 ], cost: 2 12: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg2-2*x25_1==0 && arg3>0 && arg2-2*x29_1==0 ], cost: 2 [test] deduced pseudo-invariant 3-3*arg2+2*x13_1+2*x21_1-arg1<=0, also trying -3+3*arg2-2*x13_1-2*x21_1+arg1<=-1 [test] deduced pseudo-invariant -1-3*arg2+5*x13_1-3*x21_1-2*arg1<=0, also trying 1+3*arg2-5*x13_1+3*x21_1+2*arg1<=-1 [test] deduced pseudo-invariant -x21_1<=0, also trying x21_1<=-1 Accelerated rule 8 with non-termination, yielding the new rule 13. Accelerated rule 8 with non-termination, yielding the new rule 14. Accelerated rule 8 with backward acceleration, yielding the new rule 15. Accelerated rule 8 with backward acceleration, yielding the new rule 16. Failed to prove monotonicity of the guard of rule 9. [test] deduced invariant -arg2+arg3-arg1<=0 Accelerated rule 10 with non-termination, yielding the new rule 17. Accelerated rule 10 with non-termination, yielding the new rule 18. Accelerated rule 10 with backward acceleration, yielding the new rule 19. Failed to prove monotonicity of the guard of rule 11. Failed to prove monotonicity of the guard of rule 12. [accelerate] Nesting with 4 inner and 5 outer candidates Also removing duplicate rules: 14 18. Accelerated all simple loops using metering functions (where possible): Start location: __init 8: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg3'=1+arg2+arg1, [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && 1-arg2+2*x21_1==0 ], cost: 2 9: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && arg2-2*x29_1==0 ], cost: 2 10: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg3'=1+arg2+arg1, [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 && 1-arg2+2*x21_1==0 ], cost: 2 11: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 && arg2-2*x29_1==0 ], cost: 2 12: f213_0_increase_LE -> f213_0_increase_LE : arg1'=1+arg1, arg2'=-2+arg2, arg3'=-1+arg2+arg1, [ arg1>-2 && arg2-2*x25_1==0 && arg3>0 && arg2-2*x29_1==0 ], cost: 2 13: f213_0_increase_LE -> [4] : [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && 1-arg2+2*x21_1==0 && 1+arg2+arg1>0 ], cost: NONTERM 15: f213_0_increase_LE -> [4] : [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && 1-arg2+2*x21_1==0 && 3-3*arg2+2*x13_1+2*x21_1-arg1<=0 ], cost: NONTERM 16: f213_0_increase_LE -> f213_0_increase_LE : arg1'=k+arg1, arg3'=arg2+k+arg1, [ arg1>-2 && arg2-2*x13_1<0 && arg3>0 && 1-arg2+2*x21_1==0 && -x21_1<=0 && k>=1 && -4+3*arg2-2*x13_1-2*x21_1+k+arg1<=-1 && -1+3*arg2-5*x13_1+3*x21_1+2*k+2*arg1<=-1 ], cost: 2*k 17: f213_0_increase_LE -> [4] : [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 && 1-arg2+2*x21_1==0 && 1+arg2+arg1>0 ], cost: NONTERM 19: f213_0_increase_LE -> [4] : [ arg1>-2 && arg2-2*x17_1>0 && arg3>0 && 1-arg2+2*x21_1==0 && -arg2+arg3-arg1<=0 ], cost: NONTERM 7: __init -> f213_0_increase_LE : arg1'=arg1P_1, arg2'=arg2P_1, arg3'=arg1P_1+arg2P_1, [ arg1P_1>-1 && arg2P_7>1 && arg2P_1>-1 && arg1P_7>0 ], cost: 2 Chained accelerated rules (with incoming rules): Start location: __init 7: __init -> f213_0_increase_LE : arg1'=arg1P_1, arg2'=arg2P_1, arg3'=arg1P_1+arg2P_1, [ arg1P_1>-1 && arg2P_7>1 && arg2P_1>-1 && arg1P_7>0 ], cost: 2 20: __init -> f213_0_increase_LE : arg1'=1+arg1P_1, arg2'=1+2*x21_1, arg3'=2+arg1P_1+2*x21_1, [ arg1P_1>-1 && 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 && 1+arg1P_1+2*x21_1>0 ], cost: 4 21: __init -> f213_0_increase_LE : arg1'=1+arg1P_1, arg2'=-2+2*x29_1, arg3'=-1+arg1P_1+2*x29_1, [ arg1P_1>-1 && 2*x29_1>-1 && 2*x29_1-2*x13_1<0 && arg1P_1+2*x29_1>0 ], cost: 4 22: __init -> f213_0_increase_LE : arg1'=1+arg1P_1, arg2'=1+2*x21_1, arg3'=2+arg1P_1+2*x21_1, [ arg1P_1>-1 && 1+2*x21_1>-1 && 1+2*x21_1-2*x17_1>0 && 1+arg1P_1+2*x21_1>0 ], cost: 4 23: __init -> f213_0_increase_LE : arg1'=1+arg1P_1, arg2'=-2+2*x29_1, arg3'=-1+arg1P_1+2*x29_1, [ arg1P_1>-1 && 2*x29_1>-1 && 2*x29_1-2*x17_1>0 && arg1P_1+2*x29_1>0 ], cost: 4 24: __init -> f213_0_increase_LE : arg1'=1+arg1P_1, arg2'=-2+2*x25_1, arg3'=-1+arg1P_1+2*x25_1, [ arg1P_1>-1 && 2*x25_1>-1 && arg1P_1+2*x25_1>0 ], cost: 4 25: __init -> [4] : [ 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 ], cost: NONTERM 26: __init -> [4] : [ 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 ], cost: NONTERM 27: __init -> f213_0_increase_LE : arg1'=arg1P_1+k, arg2'=1+2*x21_1, arg3'=1+arg1P_1+2*x21_1+k, [ arg1P_1>-1 && 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 && 1+arg1P_1+2*x21_1>0 && -x21_1<=0 && k>=1 && -1+arg1P_1-2*x13_1+4*x21_1+k<=-1 && 2+2*arg1P_1-5*x13_1+9*x21_1+2*k<=-1 ], cost: 2+2*k 28: __init -> [4] : [ 1+2*x21_1>-1 && 1+2*x21_1-2*x17_1>0 ], cost: NONTERM 29: __init -> [4] : [ 1+2*x21_1>-1 && 1+2*x21_1-2*x17_1>0 ], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: __init 25: __init -> [4] : [ 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 ], cost: NONTERM 26: __init -> [4] : [ 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 ], cost: NONTERM 27: __init -> f213_0_increase_LE : arg1'=arg1P_1+k, arg2'=1+2*x21_1, arg3'=1+arg1P_1+2*x21_1+k, [ arg1P_1>-1 && 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 && 1+arg1P_1+2*x21_1>0 && -x21_1<=0 && k>=1 && -1+arg1P_1-2*x13_1+4*x21_1+k<=-1 && 2+2*arg1P_1-5*x13_1+9*x21_1+2*k<=-1 ], cost: 2+2*k 28: __init -> [4] : [ 1+2*x21_1>-1 && 1+2*x21_1-2*x17_1>0 ], cost: NONTERM 29: __init -> [4] : [ 1+2*x21_1>-1 && 1+2*x21_1-2*x17_1>0 ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: __init 26: __init -> [4] : [ 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 ], cost: NONTERM 27: __init -> f213_0_increase_LE : arg1'=arg1P_1+k, arg2'=1+2*x21_1, arg3'=1+arg1P_1+2*x21_1+k, [ arg1P_1>-1 && 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 && 1+arg1P_1+2*x21_1>0 && -x21_1<=0 && k>=1 && -1+arg1P_1-2*x13_1+4*x21_1+k<=-1 && 2+2*arg1P_1-5*x13_1+9*x21_1+2*k<=-1 ], cost: 2+2*k 29: __init -> [4] : [ 1+2*x21_1>-1 && 1+2*x21_1-2*x17_1>0 ], cost: NONTERM Computing asymptotic complexity for rule 26 Guard is satisfiable, yielding nontermination Resulting cost NONTERM has complexity: Nonterm Found new complexity Nonterm. Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Nonterm Cpx degree: Nonterm Solved cost: NONTERM Rule cost: NONTERM Rule guard: [ 1+2*x21_1>-1 && 1-2*x13_1+2*x21_1<0 ] NO