The minimal system in the typelogical hierarchy NL has a polynomial recognition problem (see de Groote 1999, and Capelletti 2007 for actual parsing algorithms), but it is strictly context-free (Kandulski 1988).  Extensions with global structural rules are unsatisfactory, both on the expressivity and on the complexity front. As for L, Pentus (1993b, 2006) shows that it remains strictly context-free, whereas the addition of global associativity makes the derivability problem NP complete.  NP completeness already holds for the product-free fragment of L (Savateev 2009).  Also for LP, i.e., multiplicative intuitionistic linear logic, we have NP completeness (Kanovich 1994).  With regard to recognizing capacity, van Benthem (1995) shows that LP recognizes all permutation closures of context-free languages: a class which is too wide from the syntactic point of view.  As the logic of meaning assembly, LP is a core component of the typelogical inventory.  But as we saw in the discussion of the syntax-semantics interface, we can restrict attention to the sublanguage of LP that forms the image of derivations in syntactic calculi making interesting claims about word order and phrase structure.