Approaching Minimalist Grammars as interpreted regular tree grammars makes clear the parsing complexity of traditional chart-based parsing, and the options available for interpretation of, a derivation as a string. We found that the commonly-cited upper bound of O(n~(4k+4) was in fact too conservative, and MGs can be parsed in the much smaller polynomial time of O(n~(2k+3) · 2~k). MGs with the specifier island constraint have a parsing complexity of O(n~(2k+3)).
展开▼
