NO ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: l11 0: l0 -> l1 : __disjvr_0^0'=__disjvr_0^post_1, __disjvr_1^0'=__disjvr_1^post_1, __disjvr_2^0'=__disjvr_2^post_1, __disjvr_3^0'=__disjvr_3^post_1, b_16^0'=b_16^post_1, rt_11^0'=rt_11^post_1, st_15^0'=st_15^post_1, x_14^0'=x_14^post_1, [ 1<=x_14^0 && b_16^post_1==1 && __disjvr_0^0==__disjvr_0^post_1 && __disjvr_1^0==__disjvr_1^post_1 && __disjvr_2^0==__disjvr_2^post_1 && __disjvr_3^0==__disjvr_3^post_1 && rt_11^0==rt_11^post_1 && st_15^0==st_15^post_1 && x_14^0==x_14^post_1 ], cost: 1 3: l1 -> l5 : __disjvr_0^0'=__disjvr_0^post_4, __disjvr_1^0'=__disjvr_1^post_4, __disjvr_2^0'=__disjvr_2^post_4, __disjvr_3^0'=__disjvr_3^post_4, b_16^0'=b_16^post_4, rt_11^0'=rt_11^post_4, st_15^0'=st_15^post_4, x_14^0'=x_14^post_4, [ 0<=x_14^0 && x_14^0<=0 && rt_11^post_4==st_15^0 && __disjvr_0^0==__disjvr_0^post_4 && __disjvr_1^0==__disjvr_1^post_4 && __disjvr_2^0==__disjvr_2^post_4 && __disjvr_3^0==__disjvr_3^post_4 && b_16^0==b_16^post_4 && st_15^0==st_15^post_4 && x_14^0==x_14^post_4 ], cost: 1 4: l1 -> l6 : __disjvr_0^0'=__disjvr_0^post_5, __disjvr_1^0'=__disjvr_1^post_5, __disjvr_2^0'=__disjvr_2^post_5, __disjvr_3^0'=__disjvr_3^post_5, b_16^0'=b_16^post_5, rt_11^0'=rt_11^post_5, st_15^0'=st_15^post_5, x_14^0'=x_14^post_5, [ __disjvr_1^post_5==__disjvr_1^0 && __disjvr_0^0==__disjvr_0^post_5 && __disjvr_1^0==__disjvr_1^post_5 && __disjvr_2^0==__disjvr_2^post_5 && __disjvr_3^0==__disjvr_3^post_5 && b_16^0==b_16^post_5 && rt_11^0==rt_11^post_5 && st_15^0==st_15^post_5 && x_14^0==x_14^post_5 ], cost: 1 1: l2 -> l4 : __disjvr_0^0'=__disjvr_0^post_2, __disjvr_1^0'=__disjvr_1^post_2, __disjvr_2^0'=__disjvr_2^post_2, __disjvr_3^0'=__disjvr_3^post_2, b_16^0'=b_16^post_2, rt_11^0'=rt_11^post_2, st_15^0'=st_15^post_2, x_14^0'=x_14^post_2, [ __disjvr_0^post_2==__disjvr_0^0 && __disjvr_0^0==__disjvr_0^post_2 && __disjvr_1^0==__disjvr_1^post_2 && __disjvr_2^0==__disjvr_2^post_2 && __disjvr_3^0==__disjvr_3^post_2 && b_16^0==b_16^post_2 && rt_11^0==rt_11^post_2 && st_15^0==st_15^post_2 && x_14^0==x_14^post_2 ], cost: 1 2: l4 -> l3 : __disjvr_0^0'=__disjvr_0^post_3, __disjvr_1^0'=__disjvr_1^post_3, __disjvr_2^0'=__disjvr_2^post_3, __disjvr_3^0'=__disjvr_3^post_3, b_16^0'=b_16^post_3, rt_11^0'=rt_11^post_3, st_15^0'=st_15^post_3, x_14^0'=x_14^post_3, [ 1<=b_16^0 && b_16^0<=1 && x_14^post_3==-1+x_14^0 && b_16^post_3==0 && __disjvr_0^0==__disjvr_0^post_3 && __disjvr_1^0==__disjvr_1^post_3 && __disjvr_2^0==__disjvr_2^post_3 && __disjvr_3^0==__disjvr_3^post_3 && rt_11^0==rt_11^post_3 && st_15^0==st_15^post_3 ], cost: 1 10: l3 -> l7 : __disjvr_0^0'=__disjvr_0^post_11, __disjvr_1^0'=__disjvr_1^post_11, __disjvr_2^0'=__disjvr_2^post_11, __disjvr_3^0'=__disjvr_3^post_11, b_16^0'=b_16^post_11, rt_11^0'=rt_11^post_11, st_15^0'=st_15^post_11, x_14^0'=x_14^post_11, [ x_14^post_11==-x_14^0 && __disjvr_0^0==__disjvr_0^post_11 && __disjvr_1^0==__disjvr_1^post_11 && __disjvr_2^0==__disjvr_2^post_11 && __disjvr_3^0==__disjvr_3^post_11 && b_16^0==b_16^post_11 && rt_11^0==rt_11^post_11 && st_15^0==st_15^post_11 ], cost: 1 5: l6 -> l3 : __disjvr_0^0'=__disjvr_0^post_6, __disjvr_1^0'=__disjvr_1^post_6, __disjvr_2^0'=__disjvr_2^post_6, __disjvr_3^0'=__disjvr_3^post_6, b_16^0'=b_16^post_6, rt_11^0'=rt_11^post_6, st_15^0'=st_15^post_6, x_14^0'=x_14^post_6, [ 1<=b_16^0 && b_16^0<=1 && x_14^post_6==-1+x_14^0 && b_16^post_6==0 && __disjvr_0^0==__disjvr_0^post_6 && __disjvr_1^0==__disjvr_1^post_6 && __disjvr_2^0==__disjvr_2^post_6 && __disjvr_3^0==__disjvr_3^post_6 && rt_11^0==rt_11^post_6 && st_15^0==st_15^post_6 ], cost: 1 6: l7 -> l5 : __disjvr_0^0'=__disjvr_0^post_7, __disjvr_1^0'=__disjvr_1^post_7, __disjvr_2^0'=__disjvr_2^post_7, __disjvr_3^0'=__disjvr_3^post_7, b_16^0'=b_16^post_7, rt_11^0'=rt_11^post_7, st_15^0'=st_15^post_7, x_14^0'=x_14^post_7, [ 0<=x_14^0 && x_14^0<=0 && rt_11^post_7==st_15^0 && __disjvr_0^0==__disjvr_0^post_7 && __disjvr_1^0==__disjvr_1^post_7 && __disjvr_2^0==__disjvr_2^post_7 && __disjvr_3^0==__disjvr_3^post_7 && b_16^0==b_16^post_7 && st_15^0==st_15^post_7 && x_14^0==x_14^post_7 ], cost: 1 7: l7 -> l8 : __disjvr_0^0'=__disjvr_0^post_8, __disjvr_1^0'=__disjvr_1^post_8, __disjvr_2^0'=__disjvr_2^post_8, __disjvr_3^0'=__disjvr_3^post_8, b_16^0'=b_16^post_8, rt_11^0'=rt_11^post_8, st_15^0'=st_15^post_8, x_14^0'=x_14^post_8, [ __disjvr_2^post_8==__disjvr_2^0 && __disjvr_0^0==__disjvr_0^post_8 && __disjvr_1^0==__disjvr_1^post_8 && __disjvr_2^0==__disjvr_2^post_8 && __disjvr_3^0==__disjvr_3^post_8 && b_16^0==b_16^post_8 && rt_11^0==rt_11^post_8 && st_15^0==st_15^post_8 && x_14^0==x_14^post_8 ], cost: 1 8: l8 -> l9 : __disjvr_0^0'=__disjvr_0^post_9, __disjvr_1^0'=__disjvr_1^post_9, __disjvr_2^0'=__disjvr_2^post_9, __disjvr_3^0'=__disjvr_3^post_9, b_16^0'=b_16^post_9, rt_11^0'=rt_11^post_9, st_15^0'=st_15^post_9, x_14^0'=x_14^post_9, [ __disjvr_3^post_9==__disjvr_3^0 && __disjvr_0^0==__disjvr_0^post_9 && __disjvr_1^0==__disjvr_1^post_9 && __disjvr_2^0==__disjvr_2^post_9 && __disjvr_3^0==__disjvr_3^post_9 && b_16^0==b_16^post_9 && rt_11^0==rt_11^post_9 && st_15^0==st_15^post_9 && x_14^0==x_14^post_9 ], cost: 1 9: l9 -> l1 : __disjvr_0^0'=__disjvr_0^post_10, __disjvr_1^0'=__disjvr_1^post_10, __disjvr_2^0'=__disjvr_2^post_10, __disjvr_3^0'=__disjvr_3^post_10, b_16^0'=b_16^post_10, rt_11^0'=rt_11^post_10, st_15^0'=st_15^post_10, x_14^0'=x_14^post_10, [ x_14^1_1==1+x_14^0 && b_16^post_10==1 && x_14^post_10==-x_14^1_1 && __disjvr_0^0==__disjvr_0^post_10 && __disjvr_1^0==__disjvr_1^post_10 && __disjvr_2^0==__disjvr_2^post_10 && __disjvr_3^0==__disjvr_3^post_10 && rt_11^0==rt_11^post_10 && st_15^0==st_15^post_10 ], cost: 1 11: l10 -> l7 : __disjvr_0^0'=__disjvr_0^post_12, __disjvr_1^0'=__disjvr_1^post_12, __disjvr_2^0'=__disjvr_2^post_12, __disjvr_3^0'=__disjvr_3^post_12, b_16^0'=b_16^post_12, rt_11^0'=rt_11^post_12, st_15^0'=st_15^post_12, x_14^0'=x_14^post_12, [ x_14^post_12==-x_14^0 && __disjvr_0^0==__disjvr_0^post_12 && __disjvr_1^0==__disjvr_1^post_12 && __disjvr_2^0==__disjvr_2^post_12 && __disjvr_3^0==__disjvr_3^post_12 && b_16^0==b_16^post_12 && rt_11^0==rt_11^post_12 && st_15^0==st_15^post_12 ], cost: 1 12: l11 -> l0 : __disjvr_0^0'=__disjvr_0^post_13, __disjvr_1^0'=__disjvr_1^post_13, __disjvr_2^0'=__disjvr_2^post_13, __disjvr_3^0'=__disjvr_3^post_13, b_16^0'=b_16^post_13, rt_11^0'=rt_11^post_13, st_15^0'=st_15^post_13, x_14^0'=x_14^post_13, [ __disjvr_0^0==__disjvr_0^post_13 && __disjvr_1^0==__disjvr_1^post_13 && __disjvr_2^0==__disjvr_2^post_13 && __disjvr_3^0==__disjvr_3^post_13 && b_16^0==b_16^post_13 && rt_11^0==rt_11^post_13 && st_15^0==st_15^post_13 && x_14^0==x_14^post_13 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 12: l11 -> l0 : __disjvr_0^0'=__disjvr_0^post_13, __disjvr_1^0'=__disjvr_1^post_13, __disjvr_2^0'=__disjvr_2^post_13, __disjvr_3^0'=__disjvr_3^post_13, b_16^0'=b_16^post_13, rt_11^0'=rt_11^post_13, st_15^0'=st_15^post_13, x_14^0'=x_14^post_13, [ __disjvr_0^0==__disjvr_0^post_13 && __disjvr_1^0==__disjvr_1^post_13 && __disjvr_2^0==__disjvr_2^post_13 && __disjvr_3^0==__disjvr_3^post_13 && b_16^0==b_16^post_13 && rt_11^0==rt_11^post_13 && st_15^0==st_15^post_13 && x_14^0==x_14^post_13 ], cost: 1 Removed unreachable and leaf rules: Start location: l11 0: l0 -> l1 : __disjvr_0^0'=__disjvr_0^post_1, __disjvr_1^0'=__disjvr_1^post_1, __disjvr_2^0'=__disjvr_2^post_1, __disjvr_3^0'=__disjvr_3^post_1, b_16^0'=b_16^post_1, rt_11^0'=rt_11^post_1, st_15^0'=st_15^post_1, x_14^0'=x_14^post_1, [ 1<=x_14^0 && b_16^post_1==1 && __disjvr_0^0==__disjvr_0^post_1 && __disjvr_1^0==__disjvr_1^post_1 && __disjvr_2^0==__disjvr_2^post_1 && __disjvr_3^0==__disjvr_3^post_1 && rt_11^0==rt_11^post_1 && st_15^0==st_15^post_1 && x_14^0==x_14^post_1 ], cost: 1 4: l1 -> l6 : __disjvr_0^0'=__disjvr_0^post_5, __disjvr_1^0'=__disjvr_1^post_5, __disjvr_2^0'=__disjvr_2^post_5, __disjvr_3^0'=__disjvr_3^post_5, b_16^0'=b_16^post_5, rt_11^0'=rt_11^post_5, st_15^0'=st_15^post_5, x_14^0'=x_14^post_5, [ __disjvr_1^post_5==__disjvr_1^0 && __disjvr_0^0==__disjvr_0^post_5 && __disjvr_1^0==__disjvr_1^post_5 && __disjvr_2^0==__disjvr_2^post_5 && __disjvr_3^0==__disjvr_3^post_5 && b_16^0==b_16^post_5 && rt_11^0==rt_11^post_5 && st_15^0==st_15^post_5 && x_14^0==x_14^post_5 ], cost: 1 10: l3 -> l7 : __disjvr_0^0'=__disjvr_0^post_11, __disjvr_1^0'=__disjvr_1^post_11, __disjvr_2^0'=__disjvr_2^post_11, __disjvr_3^0'=__disjvr_3^post_11, b_16^0'=b_16^post_11, rt_11^0'=rt_11^post_11, st_15^0'=st_15^post_11, x_14^0'=x_14^post_11, [ x_14^post_11==-x_14^0 && __disjvr_0^0==__disjvr_0^post_11 && __disjvr_1^0==__disjvr_1^post_11 && __disjvr_2^0==__disjvr_2^post_11 && __disjvr_3^0==__disjvr_3^post_11 && b_16^0==b_16^post_11 && rt_11^0==rt_11^post_11 && st_15^0==st_15^post_11 ], cost: 1 5: l6 -> l3 : __disjvr_0^0'=__disjvr_0^post_6, __disjvr_1^0'=__disjvr_1^post_6, __disjvr_2^0'=__disjvr_2^post_6, __disjvr_3^0'=__disjvr_3^post_6, b_16^0'=b_16^post_6, rt_11^0'=rt_11^post_6, st_15^0'=st_15^post_6, x_14^0'=x_14^post_6, [ 1<=b_16^0 && b_16^0<=1 && x_14^post_6==-1+x_14^0 && b_16^post_6==0 && __disjvr_0^0==__disjvr_0^post_6 && __disjvr_1^0==__disjvr_1^post_6 && __disjvr_2^0==__disjvr_2^post_6 && __disjvr_3^0==__disjvr_3^post_6 && rt_11^0==rt_11^post_6 && st_15^0==st_15^post_6 ], cost: 1 7: l7 -> l8 : __disjvr_0^0'=__disjvr_0^post_8, __disjvr_1^0'=__disjvr_1^post_8, __disjvr_2^0'=__disjvr_2^post_8, __disjvr_3^0'=__disjvr_3^post_8, b_16^0'=b_16^post_8, rt_11^0'=rt_11^post_8, st_15^0'=st_15^post_8, x_14^0'=x_14^post_8, [ __disjvr_2^post_8==__disjvr_2^0 && __disjvr_0^0==__disjvr_0^post_8 && __disjvr_1^0==__disjvr_1^post_8 && __disjvr_2^0==__disjvr_2^post_8 && __disjvr_3^0==__disjvr_3^post_8 && b_16^0==b_16^post_8 && rt_11^0==rt_11^post_8 && st_15^0==st_15^post_8 && x_14^0==x_14^post_8 ], cost: 1 8: l8 -> l9 : __disjvr_0^0'=__disjvr_0^post_9, __disjvr_1^0'=__disjvr_1^post_9, __disjvr_2^0'=__disjvr_2^post_9, __disjvr_3^0'=__disjvr_3^post_9, b_16^0'=b_16^post_9, rt_11^0'=rt_11^post_9, st_15^0'=st_15^post_9, x_14^0'=x_14^post_9, [ __disjvr_3^post_9==__disjvr_3^0 && __disjvr_0^0==__disjvr_0^post_9 && __disjvr_1^0==__disjvr_1^post_9 && __disjvr_2^0==__disjvr_2^post_9 && __disjvr_3^0==__disjvr_3^post_9 && b_16^0==b_16^post_9 && rt_11^0==rt_11^post_9 && st_15^0==st_15^post_9 && x_14^0==x_14^post_9 ], cost: 1 9: l9 -> l1 : __disjvr_0^0'=__disjvr_0^post_10, __disjvr_1^0'=__disjvr_1^post_10, __disjvr_2^0'=__disjvr_2^post_10, __disjvr_3^0'=__disjvr_3^post_10, b_16^0'=b_16^post_10, rt_11^0'=rt_11^post_10, st_15^0'=st_15^post_10, x_14^0'=x_14^post_10, [ x_14^1_1==1+x_14^0 && b_16^post_10==1 && x_14^post_10==-x_14^1_1 && __disjvr_0^0==__disjvr_0^post_10 && __disjvr_1^0==__disjvr_1^post_10 && __disjvr_2^0==__disjvr_2^post_10 && __disjvr_3^0==__disjvr_3^post_10 && rt_11^0==rt_11^post_10 && st_15^0==st_15^post_10 ], cost: 1 12: l11 -> l0 : __disjvr_0^0'=__disjvr_0^post_13, __disjvr_1^0'=__disjvr_1^post_13, __disjvr_2^0'=__disjvr_2^post_13, __disjvr_3^0'=__disjvr_3^post_13, b_16^0'=b_16^post_13, rt_11^0'=rt_11^post_13, st_15^0'=st_15^post_13, x_14^0'=x_14^post_13, [ __disjvr_0^0==__disjvr_0^post_13 && __disjvr_1^0==__disjvr_1^post_13 && __disjvr_2^0==__disjvr_2^post_13 && __disjvr_3^0==__disjvr_3^post_13 && b_16^0==b_16^post_13 && rt_11^0==rt_11^post_13 && st_15^0==st_15^post_13 && x_14^0==x_14^post_13 ], cost: 1 Simplified all rules, resulting in: Start location: l11 0: l0 -> l1 : b_16^0'=1, [ 1<=x_14^0 ], cost: 1 4: l1 -> l6 : [], cost: 1 10: l3 -> l7 : x_14^0'=-x_14^0, [], cost: 1 5: l6 -> l3 : b_16^0'=0, x_14^0'=-1+x_14^0, [ 1-b_16^0==0 ], cost: 1 7: l7 -> l8 : [], cost: 1 8: l8 -> l9 : [], cost: 1 9: l9 -> l1 : b_16^0'=1, x_14^0'=-1-x_14^0, [], cost: 1 12: l11 -> l0 : [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: l11 18: l1 -> l1 : b_16^0'=1, x_14^0'=-2+x_14^0, [ 1-b_16^0==0 ], cost: 6 13: l11 -> l1 : b_16^0'=1, [ 1<=x_14^0 ], cost: 2 Accelerating simple loops of location 1. Accelerating the following rules: 18: l1 -> l1 : b_16^0'=1, x_14^0'=-2+x_14^0, [ 1-b_16^0==0 ], cost: 6 Accelerated rule 18 with non-termination, yielding the new rule 19. [accelerate] Nesting with 0 inner and 0 outer candidates Removing the simple loops: 18. Accelerated all simple loops using metering functions (where possible): Start location: l11 19: l1 -> [12] : [ 1-b_16^0==0 ], cost: NONTERM 13: l11 -> l1 : b_16^0'=1, [ 1<=x_14^0 ], cost: 2 Chained accelerated rules (with incoming rules): Start location: l11 13: l11 -> l1 : b_16^0'=1, [ 1<=x_14^0 ], cost: 2 20: l11 -> [12] : [ 1<=x_14^0 ], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: l11 20: l11 -> [12] : [ 1<=x_14^0 ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: l11 20: l11 -> [12] : [ 1<=x_14^0 ], cost: NONTERM Computing asymptotic complexity for rule 20 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_14^0 ] NO