Scholarlink

The present paper explains how to reduce the size of scattered context grammars with respect to the number of both non-context-free productions and nonterminals. It proves that every recursively enumerable language is generated by a six-nonterminal scattered context grammar with a single non-context-free production. Open problems are proposed.

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

Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Martin Havel,
  • Alexander Meduna,
  • Zbyněk Křivka

摘要

The present paper explains how to reduce the size of scattered context grammars with respect to the number of both non-context-free productions and nonterminals. It proves that every recursively enumerable language is generated by a six-nonterminal scattered context grammar with a single non-context-free production. Open problems are proposed.