Schabes (1990) reports that the universal recognition problem for TAG can be decided in time O(|G| 2 |w| 6 ), where |G| is the size of the input grammar G and |w| is the length of the input sentence w. One could hope then to efficiently solve the universal recognition problem for VW-CCG by translating an input VW-CCG G into an equivalent TAG G , and then applying to G and the input string any standard recognition method for the latter class.
the part of the equivalence proof by Vijay-Shanker and Weir (1994) showing how to translate VW-CCG to TAG requires the instantiation of a number of elementary trees in G that is exponential in |G|.