NO ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: l13 0: l0 -> l1 : WItemsNum^0'=WItemsNum^post_1, __const_5^0'=__const_5^post_1, __rho_1_^0'=__rho_1_^post_1, __rho_2_^0'=__rho_2_^post_1, [ WItemsNum^0==WItemsNum^post_1 && __const_5^0==__const_5^post_1 && __rho_1_^0==__rho_1_^post_1 && __rho_2_^0==__rho_2_^post_1 ], cost: 1 1: l1 -> l2 : WItemsNum^0'=WItemsNum^post_2, __const_5^0'=__const_5^post_2, __rho_1_^0'=__rho_1_^post_2, __rho_2_^0'=__rho_2_^post_2, [ __rho_2_^post_2==__rho_2_^post_2 && WItemsNum^0==WItemsNum^post_2 && __const_5^0==__const_5^post_2 && __rho_1_^0==__rho_1_^post_2 ], cost: 1 13: l2 -> l10 : WItemsNum^0'=WItemsNum^post_14, __const_5^0'=__const_5^post_14, __rho_1_^0'=__rho_1_^post_14, __rho_2_^0'=__rho_2_^post_14, [ 1+__const_5^0<=WItemsNum^0 && WItemsNum^0==WItemsNum^post_14 && __const_5^0==__const_5^post_14 && __rho_1_^0==__rho_1_^post_14 && __rho_2_^0==__rho_2_^post_14 ], cost: 1 14: l2 -> l11 : WItemsNum^0'=WItemsNum^post_15, __const_5^0'=__const_5^post_15, __rho_1_^0'=__rho_1_^post_15, __rho_2_^0'=__rho_2_^post_15, [ WItemsNum^0<=__const_5^0 && WItemsNum^0==WItemsNum^post_15 && __const_5^0==__const_5^post_15 && __rho_1_^0==__rho_1_^post_15 && __rho_2_^0==__rho_2_^post_15 ], cost: 1 2: l3 -> l4 : WItemsNum^0'=WItemsNum^post_3, __const_5^0'=__const_5^post_3, __rho_1_^0'=__rho_1_^post_3, __rho_2_^0'=__rho_2_^post_3, [ WItemsNum^0==WItemsNum^post_3 && __const_5^0==__const_5^post_3 && __rho_1_^0==__rho_1_^post_3 && __rho_2_^0==__rho_2_^post_3 ], cost: 1 5: l4 -> l3 : WItemsNum^0'=WItemsNum^post_6, __const_5^0'=__const_5^post_6, __rho_1_^0'=__rho_1_^post_6, __rho_2_^0'=__rho_2_^post_6, [ 3<=WItemsNum^0 && WItemsNum^post_6==-1+WItemsNum^0 && __const_5^0==__const_5^post_6 && __rho_1_^0==__rho_1_^post_6 && __rho_2_^0==__rho_2_^post_6 ], cost: 1 6: l4 -> l0 : WItemsNum^0'=WItemsNum^post_7, __const_5^0'=__const_5^post_7, __rho_1_^0'=__rho_1_^post_7, __rho_2_^0'=__rho_2_^post_7, [ WItemsNum^0<=2 && WItemsNum^0==WItemsNum^post_7 && __const_5^0==__const_5^post_7 && __rho_1_^0==__rho_1_^post_7 && __rho_2_^0==__rho_2_^post_7 ], cost: 1 3: l5 -> l6 : WItemsNum^0'=WItemsNum^post_4, __const_5^0'=__const_5^post_4, __rho_1_^0'=__rho_1_^post_4, __rho_2_^0'=__rho_2_^post_4, [ WItemsNum^0==WItemsNum^post_4 && __const_5^0==__const_5^post_4 && __rho_1_^0==__rho_1_^post_4 && __rho_2_^0==__rho_2_^post_4 ], cost: 1 4: l7 -> l8 : WItemsNum^0'=WItemsNum^post_5, __const_5^0'=__const_5^post_5, __rho_1_^0'=__rho_1_^post_5, __rho_2_^0'=__rho_2_^post_5, [ WItemsNum^0==WItemsNum^post_5 && __const_5^0==__const_5^post_5 && __rho_1_^0==__rho_1_^post_5 && __rho_2_^0==__rho_2_^post_5 ], cost: 1 7: l8 -> l9 : WItemsNum^0'=WItemsNum^post_8, __const_5^0'=__const_5^post_8, __rho_1_^0'=__rho_1_^post_8, __rho_2_^0'=__rho_2_^post_8, [ WItemsNum^0==WItemsNum^post_8 && __const_5^0==__const_5^post_8 && __rho_1_^0==__rho_1_^post_8 && __rho_2_^0==__rho_2_^post_8 ], cost: 1 8: l9 -> l8 : WItemsNum^0'=WItemsNum^post_9, __const_5^0'=__const_5^post_9, __rho_1_^0'=__rho_1_^post_9, __rho_2_^0'=__rho_2_^post_9, [ WItemsNum^0==WItemsNum^post_9 && __const_5^0==__const_5^post_9 && __rho_1_^0==__rho_1_^post_9 && __rho_2_^0==__rho_2_^post_9 ], cost: 1 9: l10 -> l1 : WItemsNum^0'=WItemsNum^post_10, __const_5^0'=__const_5^post_10, __rho_1_^0'=__rho_1_^post_10, __rho_2_^0'=__rho_2_^post_10, [ 1+__const_5^0<=WItemsNum^0 && WItemsNum^post_10==1+WItemsNum^0 && __const_5^0==__const_5^post_10 && __rho_1_^0==__rho_1_^post_10 && __rho_2_^0==__rho_2_^post_10 ], cost: 1 10: l10 -> l1 : WItemsNum^0'=WItemsNum^post_11, __const_5^0'=__const_5^post_11, __rho_1_^0'=__rho_1_^post_11, __rho_2_^0'=__rho_2_^post_11, [ WItemsNum^0<=__const_5^0 && WItemsNum^post_11==1+WItemsNum^0 && __const_5^0==__const_5^post_11 && __rho_1_^0==__rho_1_^post_11 && __rho_2_^0==__rho_2_^post_11 ], cost: 1 11: l11 -> l10 : WItemsNum^0'=WItemsNum^post_12, __const_5^0'=__const_5^post_12, __rho_1_^0'=__rho_1_^post_12, __rho_2_^0'=__rho_2_^post_12, [ __rho_2_^0<=0 && WItemsNum^0==WItemsNum^post_12 && __const_5^0==__const_5^post_12 && __rho_1_^0==__rho_1_^post_12 && __rho_2_^0==__rho_2_^post_12 ], cost: 1 12: l11 -> l3 : WItemsNum^0'=WItemsNum^post_13, __const_5^0'=__const_5^post_13, __rho_1_^0'=__rho_1_^post_13, __rho_2_^0'=__rho_2_^post_13, [ 1<=__rho_2_^0 && WItemsNum^0==WItemsNum^post_13 && __const_5^0==__const_5^post_13 && __rho_1_^0==__rho_1_^post_13 && __rho_2_^0==__rho_2_^post_13 ], cost: 1 15: l12 -> l0 : WItemsNum^0'=WItemsNum^post_16, __const_5^0'=__const_5^post_16, __rho_1_^0'=__rho_1_^post_16, __rho_2_^0'=__rho_2_^post_16, [ WItemsNum^1_1==WItemsNum^1_1 && __rho_1_^post_16==__rho_1_^post_16 && WItemsNum^post_16==__rho_1_^post_16 && __const_5^0==__const_5^post_16 && __rho_2_^0==__rho_2_^post_16 ], cost: 1 16: l13 -> l12 : WItemsNum^0'=WItemsNum^post_17, __const_5^0'=__const_5^post_17, __rho_1_^0'=__rho_1_^post_17, __rho_2_^0'=__rho_2_^post_17, [ WItemsNum^0==WItemsNum^post_17 && __const_5^0==__const_5^post_17 && __rho_1_^0==__rho_1_^post_17 && __rho_2_^0==__rho_2_^post_17 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 16: l13 -> l12 : WItemsNum^0'=WItemsNum^post_17, __const_5^0'=__const_5^post_17, __rho_1_^0'=__rho_1_^post_17, __rho_2_^0'=__rho_2_^post_17, [ WItemsNum^0==WItemsNum^post_17 && __const_5^0==__const_5^post_17 && __rho_1_^0==__rho_1_^post_17 && __rho_2_^0==__rho_2_^post_17 ], cost: 1 Removed unreachable and leaf rules: Start location: l13 0: l0 -> l1 : WItemsNum^0'=WItemsNum^post_1, __const_5^0'=__const_5^post_1, __rho_1_^0'=__rho_1_^post_1, __rho_2_^0'=__rho_2_^post_1, [ WItemsNum^0==WItemsNum^post_1 && __const_5^0==__const_5^post_1 && __rho_1_^0==__rho_1_^post_1 && __rho_2_^0==__rho_2_^post_1 ], cost: 1 1: l1 -> l2 : WItemsNum^0'=WItemsNum^post_2, __const_5^0'=__const_5^post_2, __rho_1_^0'=__rho_1_^post_2, __rho_2_^0'=__rho_2_^post_2, [ __rho_2_^post_2==__rho_2_^post_2 && WItemsNum^0==WItemsNum^post_2 && __const_5^0==__const_5^post_2 && __rho_1_^0==__rho_1_^post_2 ], cost: 1 13: l2 -> l10 : WItemsNum^0'=WItemsNum^post_14, __const_5^0'=__const_5^post_14, __rho_1_^0'=__rho_1_^post_14, __rho_2_^0'=__rho_2_^post_14, [ 1+__const_5^0<=WItemsNum^0 && WItemsNum^0==WItemsNum^post_14 && __const_5^0==__const_5^post_14 && __rho_1_^0==__rho_1_^post_14 && __rho_2_^0==__rho_2_^post_14 ], cost: 1 14: l2 -> l11 : WItemsNum^0'=WItemsNum^post_15, __const_5^0'=__const_5^post_15, __rho_1_^0'=__rho_1_^post_15, __rho_2_^0'=__rho_2_^post_15, [ WItemsNum^0<=__const_5^0 && WItemsNum^0==WItemsNum^post_15 && __const_5^0==__const_5^post_15 && __rho_1_^0==__rho_1_^post_15 && __rho_2_^0==__rho_2_^post_15 ], cost: 1 2: l3 -> l4 : WItemsNum^0'=WItemsNum^post_3, __const_5^0'=__const_5^post_3, __rho_1_^0'=__rho_1_^post_3, __rho_2_^0'=__rho_2_^post_3, [ WItemsNum^0==WItemsNum^post_3 && __const_5^0==__const_5^post_3 && __rho_1_^0==__rho_1_^post_3 && __rho_2_^0==__rho_2_^post_3 ], cost: 1 5: l4 -> l3 : WItemsNum^0'=WItemsNum^post_6, __const_5^0'=__const_5^post_6, __rho_1_^0'=__rho_1_^post_6, __rho_2_^0'=__rho_2_^post_6, [ 3<=WItemsNum^0 && WItemsNum^post_6==-1+WItemsNum^0 && __const_5^0==__const_5^post_6 && __rho_1_^0==__rho_1_^post_6 && __rho_2_^0==__rho_2_^post_6 ], cost: 1 6: l4 -> l0 : WItemsNum^0'=WItemsNum^post_7, __const_5^0'=__const_5^post_7, __rho_1_^0'=__rho_1_^post_7, __rho_2_^0'=__rho_2_^post_7, [ WItemsNum^0<=2 && WItemsNum^0==WItemsNum^post_7 && __const_5^0==__const_5^post_7 && __rho_1_^0==__rho_1_^post_7 && __rho_2_^0==__rho_2_^post_7 ], cost: 1 9: l10 -> l1 : WItemsNum^0'=WItemsNum^post_10, __const_5^0'=__const_5^post_10, __rho_1_^0'=__rho_1_^post_10, __rho_2_^0'=__rho_2_^post_10, [ 1+__const_5^0<=WItemsNum^0 && WItemsNum^post_10==1+WItemsNum^0 && __const_5^0==__const_5^post_10 && __rho_1_^0==__rho_1_^post_10 && __rho_2_^0==__rho_2_^post_10 ], cost: 1 10: l10 -> l1 : WItemsNum^0'=WItemsNum^post_11, __const_5^0'=__const_5^post_11, __rho_1_^0'=__rho_1_^post_11, __rho_2_^0'=__rho_2_^post_11, [ WItemsNum^0<=__const_5^0 && WItemsNum^post_11==1+WItemsNum^0 && __const_5^0==__const_5^post_11 && __rho_1_^0==__rho_1_^post_11 && __rho_2_^0==__rho_2_^post_11 ], cost: 1 11: l11 -> l10 : WItemsNum^0'=WItemsNum^post_12, __const_5^0'=__const_5^post_12, __rho_1_^0'=__rho_1_^post_12, __rho_2_^0'=__rho_2_^post_12, [ __rho_2_^0<=0 && WItemsNum^0==WItemsNum^post_12 && __const_5^0==__const_5^post_12 && __rho_1_^0==__rho_1_^post_12 && __rho_2_^0==__rho_2_^post_12 ], cost: 1 12: l11 -> l3 : WItemsNum^0'=WItemsNum^post_13, __const_5^0'=__const_5^post_13, __rho_1_^0'=__rho_1_^post_13, __rho_2_^0'=__rho_2_^post_13, [ 1<=__rho_2_^0 && WItemsNum^0==WItemsNum^post_13 && __const_5^0==__const_5^post_13 && __rho_1_^0==__rho_1_^post_13 && __rho_2_^0==__rho_2_^post_13 ], cost: 1 15: l12 -> l0 : WItemsNum^0'=WItemsNum^post_16, __const_5^0'=__const_5^post_16, __rho_1_^0'=__rho_1_^post_16, __rho_2_^0'=__rho_2_^post_16, [ WItemsNum^1_1==WItemsNum^1_1 && __rho_1_^post_16==__rho_1_^post_16 && WItemsNum^post_16==__rho_1_^post_16 && __const_5^0==__const_5^post_16 && __rho_2_^0==__rho_2_^post_16 ], cost: 1 16: l13 -> l12 : WItemsNum^0'=WItemsNum^post_17, __const_5^0'=__const_5^post_17, __rho_1_^0'=__rho_1_^post_17, __rho_2_^0'=__rho_2_^post_17, [ WItemsNum^0==WItemsNum^post_17 && __const_5^0==__const_5^post_17 && __rho_1_^0==__rho_1_^post_17 && __rho_2_^0==__rho_2_^post_17 ], cost: 1 Simplified all rules, resulting in: Start location: l13 0: l0 -> l1 : [], cost: 1 1: l1 -> l2 : __rho_2_^0'=__rho_2_^post_2, [], cost: 1 13: l2 -> l10 : [ 1+__const_5^0<=WItemsNum^0 ], cost: 1 14: l2 -> l11 : [ WItemsNum^0<=__const_5^0 ], cost: 1 2: l3 -> l4 : [], cost: 1 5: l4 -> l3 : WItemsNum^0'=-1+WItemsNum^0, [ 3<=WItemsNum^0 ], cost: 1 6: l4 -> l0 : [ WItemsNum^0<=2 ], cost: 1 9: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ 1+__const_5^0<=WItemsNum^0 ], cost: 1 10: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ WItemsNum^0<=__const_5^0 ], cost: 1 11: l11 -> l10 : [ __rho_2_^0<=0 ], cost: 1 12: l11 -> l3 : [ 1<=__rho_2_^0 ], cost: 1 15: l12 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 1 16: l13 -> l12 : [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: l13 0: l0 -> l1 : [], cost: 1 1: l1 -> l2 : __rho_2_^0'=__rho_2_^post_2, [], cost: 1 13: l2 -> l10 : [ 1+__const_5^0<=WItemsNum^0 ], cost: 1 14: l2 -> l11 : [ WItemsNum^0<=__const_5^0 ], cost: 1 2: l3 -> l4 : [], cost: 1 5: l4 -> l3 : WItemsNum^0'=-1+WItemsNum^0, [ 3<=WItemsNum^0 ], cost: 1 6: l4 -> l0 : [ WItemsNum^0<=2 ], cost: 1 9: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ 1+__const_5^0<=WItemsNum^0 ], cost: 1 10: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ WItemsNum^0<=__const_5^0 ], cost: 1 11: l11 -> l10 : [ __rho_2_^0<=0 ], cost: 1 12: l11 -> l3 : [ 1<=__rho_2_^0 ], cost: 1 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Eliminated locations (on tree-shaped paths): Start location: l13 0: l0 -> l1 : [], cost: 1 18: l1 -> l10 : __rho_2_^0'=__rho_2_^post_2, [ 1+__const_5^0<=WItemsNum^0 ], cost: 2 19: l1 -> l11 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 ], cost: 2 20: l3 -> l3 : WItemsNum^0'=-1+WItemsNum^0, [ 3<=WItemsNum^0 ], cost: 2 21: l3 -> l0 : [ WItemsNum^0<=2 ], cost: 2 9: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ 1+__const_5^0<=WItemsNum^0 ], cost: 1 10: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ WItemsNum^0<=__const_5^0 ], cost: 1 11: l11 -> l10 : [ __rho_2_^0<=0 ], cost: 1 12: l11 -> l3 : [ 1<=__rho_2_^0 ], cost: 1 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Accelerating simple loops of location 3. Accelerating the following rules: 20: l3 -> l3 : WItemsNum^0'=-1+WItemsNum^0, [ 3<=WItemsNum^0 ], cost: 2 Accelerated rule 20 with backward acceleration, yielding the new rule 22. [accelerate] Nesting with 1 inner and 1 outer candidates Removing the simple loops: 20. Accelerated all simple loops using metering functions (where possible): Start location: l13 0: l0 -> l1 : [], cost: 1 18: l1 -> l10 : __rho_2_^0'=__rho_2_^post_2, [ 1+__const_5^0<=WItemsNum^0 ], cost: 2 19: l1 -> l11 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 ], cost: 2 21: l3 -> l0 : [ WItemsNum^0<=2 ], cost: 2 22: l3 -> l3 : WItemsNum^0'=2, [ -2+WItemsNum^0>=0 ], cost: -4+2*WItemsNum^0 9: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ 1+__const_5^0<=WItemsNum^0 ], cost: 1 10: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ WItemsNum^0<=__const_5^0 ], cost: 1 11: l11 -> l10 : [ __rho_2_^0<=0 ], cost: 1 12: l11 -> l3 : [ 1<=__rho_2_^0 ], cost: 1 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Chained accelerated rules (with incoming rules): Start location: l13 0: l0 -> l1 : [], cost: 1 18: l1 -> l10 : __rho_2_^0'=__rho_2_^post_2, [ 1+__const_5^0<=WItemsNum^0 ], cost: 2 19: l1 -> l11 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 ], cost: 2 21: l3 -> l0 : [ WItemsNum^0<=2 ], cost: 2 9: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ 1+__const_5^0<=WItemsNum^0 ], cost: 1 10: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ WItemsNum^0<=__const_5^0 ], cost: 1 11: l11 -> l10 : [ __rho_2_^0<=0 ], cost: 1 12: l11 -> l3 : [ 1<=__rho_2_^0 ], cost: 1 23: l11 -> l3 : WItemsNum^0'=2, [ 1<=__rho_2_^0 && -2+WItemsNum^0>=0 ], cost: -3+2*WItemsNum^0 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Eliminated locations (on tree-shaped paths): Start location: l13 0: l0 -> l1 : [], cost: 1 18: l1 -> l10 : __rho_2_^0'=__rho_2_^post_2, [ 1+__const_5^0<=WItemsNum^0 ], cost: 2 24: l1 -> l10 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && __rho_2_^post_2<=0 ], cost: 3 25: l1 -> l3 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 ], cost: 3 26: l1 -> l3 : WItemsNum^0'=2, __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && -2+WItemsNum^0>=0 ], cost: -1+2*WItemsNum^0 21: l3 -> l0 : [ WItemsNum^0<=2 ], cost: 2 9: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ 1+__const_5^0<=WItemsNum^0 ], cost: 1 10: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [ WItemsNum^0<=__const_5^0 ], cost: 1 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Merged rules: Start location: l13 0: l0 -> l1 : [], cost: 1 18: l1 -> l10 : __rho_2_^0'=__rho_2_^post_2, [ 1+__const_5^0<=WItemsNum^0 ], cost: 2 24: l1 -> l10 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && __rho_2_^post_2<=0 ], cost: 3 25: l1 -> l3 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 ], cost: 3 26: l1 -> l3 : WItemsNum^0'=2, __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && -2+WItemsNum^0>=0 ], cost: -1+2*WItemsNum^0 21: l3 -> l0 : [ WItemsNum^0<=2 ], cost: 2 27: l10 -> l1 : WItemsNum^0'=1+WItemsNum^0, [], cost: 1 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Eliminated locations (on tree-shaped paths): Start location: l13 0: l0 -> l1 : [], cost: 1 28: l1 -> l0 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && WItemsNum^0<=2 ], cost: 5 29: l1 -> l0 : WItemsNum^0'=2, __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && -2+WItemsNum^0>=0 ], cost: 1+2*WItemsNum^0 30: l1 -> l1 : WItemsNum^0'=1+WItemsNum^0, __rho_2_^0'=__rho_2_^post_2, [ 1+__const_5^0<=WItemsNum^0 ], cost: 3 31: l1 -> l1 : WItemsNum^0'=1+WItemsNum^0, __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && __rho_2_^post_2<=0 ], cost: 4 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Accelerating simple loops of location 1. Accelerating the following rules: 30: l1 -> l1 : WItemsNum^0'=1+WItemsNum^0, __rho_2_^0'=__rho_2_^post_2, [ 1+__const_5^0<=WItemsNum^0 ], cost: 3 31: l1 -> l1 : WItemsNum^0'=1+WItemsNum^0, __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && __rho_2_^post_2<=0 ], cost: 4 Accelerated rule 30 with non-termination, yielding the new rule 32. Accelerated rule 31 with backward acceleration, yielding the new rule 33. [accelerate] Nesting with 1 inner and 1 outer candidates Removing the simple loops: 30 31. Accelerated all simple loops using metering functions (where possible): Start location: l13 0: l0 -> l1 : [], cost: 1 28: l1 -> l0 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && WItemsNum^0<=2 ], cost: 5 29: l1 -> l0 : WItemsNum^0'=2, __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && -2+WItemsNum^0>=0 ], cost: 1+2*WItemsNum^0 32: l1 -> [15] : [ 1+__const_5^0<=WItemsNum^0 ], cost: NONTERM 33: l1 -> l1 : WItemsNum^0'=1+__const_5^0, __rho_2_^0'=__rho_2_^post_2, [ __rho_2_^post_2<=0 && 1+__const_5^0-WItemsNum^0>=1 ], cost: 4+4*__const_5^0-4*WItemsNum^0 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Chained accelerated rules (with incoming rules): Start location: l13 0: l0 -> l1 : [], cost: 1 34: l0 -> [15] : [ 1+__const_5^0<=WItemsNum^0 ], cost: NONTERM 35: l0 -> l1 : WItemsNum^0'=1+__const_5^0, __rho_2_^0'=__rho_2_^post_2, [ __rho_2_^post_2<=0 && 1+__const_5^0-WItemsNum^0>=1 ], cost: 5+4*__const_5^0-4*WItemsNum^0 28: l1 -> l0 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && WItemsNum^0<=2 ], cost: 5 29: l1 -> l0 : WItemsNum^0'=2, __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && -2+WItemsNum^0>=0 ], cost: 1+2*WItemsNum^0 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Eliminated locations (on tree-shaped paths): Start location: l13 34: l0 -> [15] : [ 1+__const_5^0<=WItemsNum^0 ], cost: NONTERM 36: l0 -> l0 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && WItemsNum^0<=2 ], cost: 6 37: l0 -> l0 : WItemsNum^0'=2, __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && -2+WItemsNum^0>=0 ], cost: 2+2*WItemsNum^0 38: l0 -> [16] : [ __rho_2_^post_2<=0 && 1+__const_5^0-WItemsNum^0>=1 ], cost: 5+4*__const_5^0-4*WItemsNum^0 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Accelerating simple loops of location 0. Accelerating the following rules: 36: l0 -> l0 : __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && WItemsNum^0<=2 ], cost: 6 37: l0 -> l0 : WItemsNum^0'=2, __rho_2_^0'=__rho_2_^post_2, [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && -2+WItemsNum^0>=0 ], cost: 2+2*WItemsNum^0 Accelerated rule 36 with non-termination, yielding the new rule 39. Accelerated rule 37 with non-termination, yielding the new rule 40. [accelerate] Nesting with 0 inner and 0 outer candidates Removing the simple loops: 36 37. Accelerated all simple loops using metering functions (where possible): Start location: l13 34: l0 -> [15] : [ 1+__const_5^0<=WItemsNum^0 ], cost: NONTERM 38: l0 -> [16] : [ __rho_2_^post_2<=0 && 1+__const_5^0-WItemsNum^0>=1 ], cost: 5+4*__const_5^0-4*WItemsNum^0 39: l0 -> [17] : [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && WItemsNum^0<=2 ], cost: NONTERM 40: l0 -> [17] : [ WItemsNum^0<=__const_5^0 && 1<=__rho_2_^post_2 && -2+WItemsNum^0>=0 ], cost: NONTERM 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 Chained accelerated rules (with incoming rules): Start location: l13 34: l0 -> [15] : [ 1+__const_5^0<=WItemsNum^0 ], cost: NONTERM 38: l0 -> [16] : [ __rho_2_^post_2<=0 && 1+__const_5^0-WItemsNum^0>=1 ], cost: 5+4*__const_5^0-4*WItemsNum^0 17: l13 -> l0 : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [], cost: 2 41: l13 -> [17] : [], cost: NONTERM 42: l13 -> [17] : [ 2<=__const_5^0 ], cost: NONTERM Eliminated locations (on tree-shaped paths): Start location: l13 41: l13 -> [17] : [], cost: NONTERM 42: l13 -> [17] : [ 2<=__const_5^0 ], cost: NONTERM 43: l13 -> [15] : [ 1+__const_5^0<=WItemsNum^post_16 ], cost: NONTERM 44: l13 -> [16] : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [ __rho_2_^post_2<=0 && 1+__const_5^0-WItemsNum^post_16>=1 ], cost: 7+4*__const_5^0-4*WItemsNum^post_16 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: l13 41: l13 -> [17] : [], cost: NONTERM 42: l13 -> [17] : [ 2<=__const_5^0 ], cost: NONTERM 43: l13 -> [15] : [ 1+__const_5^0<=WItemsNum^post_16 ], cost: NONTERM 44: l13 -> [16] : WItemsNum^0'=WItemsNum^post_16, __rho_1_^0'=WItemsNum^post_16, [ __rho_2_^post_2<=0 && 1+__const_5^0-WItemsNum^post_16>=1 ], cost: 7+4*__const_5^0-4*WItemsNum^post_16 Computing asymptotic complexity for rule 41 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: [] NO