Ristad (1986a) examines the computational complexity of two components of the G P S G formal system (metarules and the feature system) and shows how each of these systems can lead to computational intractability. Rlstad also proves that the universal recognition problem for G P S G s is E X P - P O L Y hard, and In another words, the fastest recognition algorithm for G P S G s can take more than exponential time. These results m a y appear surprising, given GPSG's weak context-fres generative power. .
