Memory requirements and local ambiguities of parsing strategies

We present a method for calculating lower bounds on the space required and local ambiguities entailed by parsing strategies. A fast, compact natural language parser must implement a strategy with low space requirements and few local ambiguities. It is also widely assumed in the psycholinguistics literature that extremely limited short-term space is available to the human parser, and that sentences containing center-embedded constructions are incomprehensible because processing them requires more space than is available. However, we show that the parsing strategies most psycholinguists assume require less space for processing center-embedded constructions than for processing other perfectly comprehensible constructions. We present alternative strategies for which center-embedded constructions do require more space than other constructions.