Scholarlink

Graph-controlled insertion-deletion (GCID) systems are regulated extensions of insertion-deletion systems. At AFL 2023, we introduced star-controlled GCID systems as a restriction of GCID systems where there is a special component, namely, a central component that will process the string and then send it to any other component that processes another step and then send the string back to the central component. With this restriction, here we obtain three new, different computational completeness results for some typical descriptional complexity measures. These results are crucially based on a variant of Special Geffert normal form (SGNF) of type-0 grammars, that we called space separating SGNF in a paper that appeared in Natural Computing in 2019.

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

Succinct Star-Controlled Insertion-Deletion Systems Using Space Separating Normal Forms

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Henning Fernau,
  • Lakshmanan Kuppusamy,
  • Indhumathi Raman

摘要

Graph-controlled insertion-deletion (GCID) systems are regulated extensions of insertion-deletion systems. At AFL 2023, we introduced star-controlled GCID systems as a restriction of GCID systems where there is a special component, namely, a central component that will process the string and then send it to any other component that processes another step and then send the string back to the central component. With this restriction, here we obtain three new, different computational completeness results for some typical descriptional complexity measures. These results are crucially based on a variant of Special Geffert normal form (SGNF) of type-0 grammars, that we called space separating SGNF in a paper that appeared in Natural Computing in 2019.