S4 enriched multimodal categorial grammars are context-free: Corrigendum
Plummer [A.R. Plummer, S4 enriched multimodal categorial grammars are context-free, Theoretical Computer Science 388 (2007) 173-180] showed that categorial grammars based on NLS4, the non-associative multimodal Lambek calculus enriched with S4 axioms, weakly recognize context-free languages. However, the proof contains a gap. We correct the earlier proof, utilizing a technique given in Buszkowski [W. Buszkowski, Lambek calculus with nonlogical axioms, in: C. Casadio, P.J. Scott, R.A.G. Seely (Eds.), Language and Grammar: Studies in Mathematical Linguistics and Natural Language, in: Lecture Notes, vol. 168, Center for the Study of Language and Information, Stanford, 2005, pp. 77-93]. This technique immediately proves that NLS4 is decidable in polynomial time. (C) 2008 Elsevier B.V. All rights reserved.
s4 categorial grammar context-free language lambek grammar multimodal grammar chomsky hierarchy