### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f0 -> f : [ x>y^2 ], cost: y Added constraints to the guards to ensure costs are nonnegative: Start location: f0 0: f0 -> f : [ x>y^2 && y>=0 ], cost: y Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: f0 -> f : [ x>y^2 && y>=0 ], cost: y ### Simplification by acceleration and chaining ### ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 0: f0 -> f : [ x>y^2 && y>=0 ], cost: y Computing asymptotic complexity for rule 0 Solved the limit problem by the following transformations: Created initial limit problem: 1+y (+/+!), y (+), x-y^2 (+/+!) [not solved] applying transformation rule (C) using substitution {x==1+y^2} resulting limit problem: 1 (+/+!), 1+y (+/+!), y (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 1+y (+/+!), y (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {y==n} resulting limit problem: [solved] Solution: x / 1+n^2 y / n Resulting cost n has complexity: Poly(n^(1/2)) Found new complexity Poly(n^(1/2)). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^(1/2)) Cpx degree: 0.5 Solved cost: n Rule cost: y Rule guard: [ x>y^2 && y>=0 ] WORST_CASE(Omega(n^(1/2)),?)