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