We prove several results on the expressive power of Lambek categorial grammars extended with Kleene star. Namely, for the systems with the omega-rule and with inductive-style axiomatisations we prove undecidability (negative) results, showing that such grammars are capable of generating some universal classes of languages. On the other hand, however, we show context-freeness for a restricted case, extending a result of Buszkowski and Palka (2008).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Lambek Grammars with Kleene Star

  • Stepan L. Kuznetsov

摘要

We prove several results on the expressive power of Lambek categorial grammars extended with Kleene star. Namely, for the systems with the omega-rule and with inductive-style axiomatisations we prove undecidability (negative) results, showing that such grammars are capable of generating some universal classes of languages. On the other hand, however, we show context-freeness for a restricted case, extending a result of Buszkowski and Palka (2008).