NO ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: l4 0: l0 -> l1 : x_5^0'=x_5^post_1, [ x_5^0==x_5^post_1 ], cost: 1 1: l1 -> l2 : x_5^0'=x_5^post_2, [ x_5^post_2==-1+x_5^0 && x_5^post_2<=0 ], cost: 1 3: l1 -> l3 : x_5^0'=x_5^post_4, [ x_5^post_4==-1+x_5^0 && 0<=-1+x_5^post_4 ], cost: 1 2: l2 -> l1 : x_5^0'=x_5^post_3, [ x_5^0==x_5^post_3 ], cost: 1 4: l3 -> l1 : x_5^0'=x_5^post_5, [ x_5^0==x_5^post_5 ], cost: 1 5: l4 -> l0 : x_5^0'=x_5^post_6, [ x_5^0==x_5^post_6 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 5: l4 -> l0 : x_5^0'=x_5^post_6, [ x_5^0==x_5^post_6 ], cost: 1 Simplified all rules, resulting in: Start location: l4 0: l0 -> l1 : [], cost: 1 1: l1 -> l2 : x_5^0'=-1+x_5^0, [ -1+x_5^0<=0 ], cost: 1 3: l1 -> l3 : x_5^0'=-1+x_5^0, [ 0<=-2+x_5^0 ], cost: 1 2: l2 -> l1 : [], cost: 1 4: l3 -> l1 : [], cost: 1 5: l4 -> l0 : [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: l4 7: l1 -> l1 : x_5^0'=-1+x_5^0, [ -1+x_5^0<=0 ], cost: 2 8: l1 -> l1 : x_5^0'=-1+x_5^0, [ 0<=-2+x_5^0 ], cost: 2 6: l4 -> l1 : [], cost: 2 Accelerating simple loops of location 1. Accelerating the following rules: 7: l1 -> l1 : x_5^0'=-1+x_5^0, [ -1+x_5^0<=0 ], cost: 2 8: l1 -> l1 : x_5^0'=-1+x_5^0, [ 0<=-2+x_5^0 ], cost: 2 Accelerated rule 7 with non-termination, yielding the new rule 9. Accelerated rule 8 with backward acceleration, yielding the new rule 10. [accelerate] Nesting with 1 inner and 1 outer candidates Removing the simple loops: 7 8. Accelerated all simple loops using metering functions (where possible): Start location: l4 9: l1 -> [5] : [ -1+x_5^0<=0 ], cost: NONTERM 10: l1 -> l1 : x_5^0'=1, [ -1+x_5^0>=0 ], cost: -2+2*x_5^0 6: l4 -> l1 : [], cost: 2 Chained accelerated rules (with incoming rules): Start location: l4 6: l4 -> l1 : [], cost: 2 11: l4 -> [5] : [ -1+x_5^0<=0 ], cost: NONTERM 12: l4 -> l1 : x_5^0'=1, [ -1+x_5^0>=0 ], cost: 2*x_5^0 Removed unreachable locations (and leaf rules with constant cost): Start location: l4 11: l4 -> [5] : [ -1+x_5^0<=0 ], cost: NONTERM 12: l4 -> l1 : x_5^0'=1, [ -1+x_5^0>=0 ], cost: 2*x_5^0 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: l4 11: l4 -> [5] : [ -1+x_5^0<=0 ], cost: NONTERM 12: l4 -> l1 : x_5^0'=1, [ -1+x_5^0>=0 ], cost: 2*x_5^0 Computing asymptotic complexity for rule 11 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+x_5^0<=0 ] NO