Scholarlink

<p>Generalized communicating P systems (GCPSs for short) are a common generalization of tissue-like P systems (networks of cells) where each interaction rule can move only two objects through the cells. Depending on the source and target cells, nine types of such rules are distinguished. Previous works have shown that several GCPSs families where the GCPSs use only one type of rules and have only three cells are computationally complete devices. In this paper, we show that GCPSs with only parallel-shift rules and only four cells, and GCPSs with only presence-move rules and only three cells are computationally complete as well. With these new results, we contribute to the research goal of providing a sharp lower bound on the number of cells needed to achieve computational completeness for all families of GCPSs where GCPSs use only one type of interaction rules. </p>

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

Computational completeness of minimal communication with small number of cells

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年5月5日

查看全文
  • Erzsébet Csuhaj-Varjú,
  • Sergey Verlan

摘要

Generalized communicating P systems (GCPSs for short) are a common generalization of tissue-like P systems (networks of cells) where each interaction rule can move only two objects through the cells. Depending on the source and target cells, nine types of such rules are distinguished. Previous works have shown that several GCPSs families where the GCPSs use only one type of rules and have only three cells are computationally complete devices. In this paper, we show that GCPSs with only parallel-shift rules and only four cells, and GCPSs with only presence-move rules and only three cells are computationally complete as well. With these new results, we contribute to the research goal of providing a sharp lower bound on the number of cells needed to achieve computational completeness for all families of GCPSs where GCPSs use only one type of interaction rules.