Scholarlink

Abstract <p>This work examines basic categorial grammars and categorial grammars with the unique type assignment condition. For the first formalism, it is proven that determining for an arbitrary context-free language <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(L\)</EquationSource> <!--DANMath2570018Vishnikin-m1--> </InlineEquation> whether it is generated by some grammar from this class is algorithmically undecidable. It is also proven that, for any two grammars of this class, the problem of determining the emptiness of the intersection of the languages generated by these grammars is algorithmically undecidable. For the second formalism, it is proven that, for any two categorial grammars with unique type assignment, the problem of determining language inclusion is algorithmically undecidable.</p>

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

Algorithmic Properties of Basic Categorial Grammars with Unique Category Assignment

  • 期刊论文

  • 发表日期：

    2025年6月1日

查看全文
  • M. E. Vishnikin

摘要

Abstract

This work examines basic categorial grammars and categorial grammars with the unique type assignment condition. For the first formalism, it is proven that determining for an arbitrary context-free language \(L\) whether it is generated by some grammar from this class is algorithmically undecidable. It is also proven that, for any two grammars of this class, the problem of determining the emptiness of the intersection of the languages generated by these grammars is algorithmically undecidable. For the second formalism, it is proven that, for any two categorial grammars with unique type assignment, the problem of determining language inclusion is algorithmically undecidable.