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