WORST_CASE(Omega(1),?) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: __init 0: f1_0_main_Load -> f82_0_loop_EQ : arg1'=arg1P_1, arg2'=arg2P_1, [ arg1>0 && arg2>-1 && arg2==arg1P_1 ], cost: 1 1: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=arg1P_2, arg2'=arg2P_2, [ arg1<2 && arg1<-5 && arg1<0 && 1-arg1==arg1P_2 ], cost: 1 2: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=arg1P_3, arg2'=arg2P_3, [ arg1<2 && arg1<-5 && arg1>0 && 1-arg1==arg1P_3 ], cost: 1 3: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=arg1P_4, arg2'=arg2P_4, [ arg1<6 && arg1>-6 && arg1<0 && 0==arg1P_4 ], cost: 1 4: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=arg1P_5, arg2'=arg2P_5, [ arg1<6 && arg1>0 && 0==arg1P_5 ], cost: 1 5: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=arg1P_6, arg2'=arg2P_6, [ arg1>5 && -1-arg1==arg1P_6 ], cost: 1 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_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, [], cost: 1 Removed rules with unsatisfiable guard: Start location: __init 0: f1_0_main_Load -> f82_0_loop_EQ : arg1'=arg1P_1, arg2'=arg2P_1, [ arg1>0 && arg2>-1 && arg2==arg1P_1 ], cost: 1 1: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=arg1P_2, arg2'=arg2P_2, [ arg1<2 && arg1<-5 && arg1<0 && 1-arg1==arg1P_2 ], cost: 1 3: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=arg1P_4, arg2'=arg2P_4, [ arg1<6 && arg1>-6 && arg1<0 && 0==arg1P_4 ], cost: 1 4: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=arg1P_5, arg2'=arg2P_5, [ arg1<6 && arg1>0 && 0==arg1P_5 ], cost: 1 5: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=arg1P_6, arg2'=arg2P_6, [ arg1>5 && -1-arg1==arg1P_6 ], cost: 1 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 Simplified all rules, resulting in: Start location: __init 0: f1_0_main_Load -> f82_0_loop_EQ : arg1'=arg2, arg2'=arg2P_1, [ arg1>0 && arg2>-1 ], cost: 1 1: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=1-arg1, arg2'=arg2P_2, [ arg1<-5 ], cost: 1 3: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_4, [ arg1>-6 && arg1<0 ], cost: 1 4: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_5, [ arg1<6 && arg1>0 ], cost: 1 5: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=-1-arg1, arg2'=arg2P_6, [ arg1>5 ], cost: 1 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=1-arg1, arg2'=arg2P_2, [ arg1<-5 ], cost: 1 3: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_4, [ arg1>-6 && arg1<0 ], cost: 1 4: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_5, [ arg1<6 && arg1>0 ], cost: 1 5: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=-1-arg1, arg2'=arg2P_6, [ arg1>5 ], cost: 1 Found no metering function for rule 1. Accelerated rule 3 with metering function meter (where 5*meter==-arg1), yielding the new rule 7. Accelerated rule 4 with metering function meter_1 (where 5*meter_1==arg1), yielding the new rule 8. Found no metering function for rule 5. Removing the simple loops: 3 4. Accelerated all simple loops using metering functions (where possible): Start location: __init 0: f1_0_main_Load -> f82_0_loop_EQ : arg1'=arg2, arg2'=arg2P_1, [ arg1>0 && arg2>-1 ], cost: 1 1: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=1-arg1, arg2'=arg2P_2, [ arg1<-5 ], cost: 1 5: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=-1-arg1, arg2'=arg2P_6, [ arg1>5 ], cost: 1 7: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_4, [ arg1>-6 && arg1<0 && 5*meter==-arg1 && meter>=1 ], cost: meter 8: f82_0_loop_EQ -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_5, [ arg1<6 && arg1>0 && 5*meter_1==arg1 && meter_1>=1 ], cost: meter_1 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: __init 0: f1_0_main_Load -> f82_0_loop_EQ : arg1'=arg2, arg2'=arg2P_1, [ arg1>0 && arg2>-1 ], cost: 1 9: f1_0_main_Load -> f82_0_loop_EQ : arg1'=-1-arg2, arg2'=arg2P_6, [ arg1>0 && arg2>5 ], cost: 2 10: f1_0_main_Load -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_5, [ arg1>0 && arg2<6 && arg2>0 && 5*meter_1==arg2 && meter_1>=1 ], cost: 1+meter_1 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 Removed unreachable locations (and leaf rules with constant cost): Start location: __init 10: f1_0_main_Load -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_5, [ arg1>0 && arg2<6 && arg2>0 && 5*meter_1==arg2 && meter_1>=1 ], cost: 1+meter_1 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 Eliminated locations (on linear paths): Start location: __init 11: __init -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_5, [ arg1P_7>0 && arg2P_7<6 && arg2P_7>0 && 5*meter_1==arg2P_7 && meter_1>=1 ], cost: 2+meter_1 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: __init 11: __init -> f82_0_loop_EQ : arg1'=0, arg2'=arg2P_5, [ arg1P_7>0 && arg2P_7<6 && arg2P_7>0 && 5*meter_1==arg2P_7 && meter_1>=1 ], cost: 2+meter_1 Computing asymptotic complexity for rule 11 Could not solve the limit problem. Resulting cost 0 has complexity: Unknown Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Constant Cpx degree: 0 Solved cost: 1 Rule cost: 1 Rule guard: [] WORST_CASE(Omega(1),?)