WORST_CASE(Omega(0),?) Initial ITS Start location: l1 0: l1 -> l0 : 0 <= 0, cost: 1 Removed unreachable rules and leafs Start location: l1 Computing asymptotic complexity Proved the following lower bound Complexity: Unknown Cpx degree: ? Solved cost: 0 Rule cost: 0