As such, we are able to support the findings of Rajasekaran and Yooseph (1998), who showed that tree-adjoining grammar (TAG) recognition can be done in time O(M(n 2 )) = O(n 4.76 ) (TAG can be reduced to LCFRS with d = 2).
combinatory categorial grammars, head grammars, and linear indexed grammars can be recognized in time O(M(n 2 )).