DEXPTIME is Deterministic Expotential Time ie it is the same as O(2^n) for time (time is the most frequently used measure of complexity but there are others and among them is space). So I really should have written that ML grammar is expotential in the worst case too.