Scholarlink

<p>In this paper, we consider prescribed sets of rules working on several objects either in parallel—in this case the rules have to take different objects—or else sequentially in any order—in this case several rules may take the same object to work on. As specific rules, we use the insertion and deletion rules at the end of strings. We show the optimal result that systems of degree two, i.e., with only two initial strings, using prescribed teams of size two, i.e., containing exactly two rules, are sufficient to obtain computational completeness, with very simple rules either allowing for inserting a symbol&#xa0;<i>b</i> on the right-hand side of a string ending with a symbol&#xa0;<i>a</i> or else deleting a symbol&#xa0;<i>b</i> on the right-hand side of a string. Similar results hold when using the corresponding insertion and deletion rules on the left-hand side of strings. Using only such rules on either side of strings, with systems of degree one exactly the regular languages can be generated, whereas with systems of size one (and arbitrary degree) we even cannot obtain all regular languages. Moreover, we establish corresponding results when considering linear membrane structures as objects and using rules which put a membrane with label&#xa0;<i>b</i> around a linear membrane object with the outermost membrane labeled by&#xa0;<i>a</i> or else erase the outermost membrane labeled by&#xa0;<i>b</i> of a linear membrane object.</p>

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

Prescribed teams of insertion and deletion rules working on different objects

  • 期刊论文

  • 发表日期：

    2025年8月4日

查看全文
  • Artiom Alhazov,
  • Rudolf Freund,
  • Sergiu Ivanov,
  • Sergey Verlan

摘要

In this paper, we consider prescribed sets of rules working on several objects either in parallel—in this case the rules have to take different objects—or else sequentially in any order—in this case several rules may take the same object to work on. As specific rules, we use the insertion and deletion rules at the end of strings. We show the optimal result that systems of degree two, i.e., with only two initial strings, using prescribed teams of size two, i.e., containing exactly two rules, are sufficient to obtain computational completeness, with very simple rules either allowing for inserting a symbol b on the right-hand side of a string ending with a symbol a or else deleting a symbol b on the right-hand side of a string. Similar results hold when using the corresponding insertion and deletion rules on the left-hand side of strings. Using only such rules on either side of strings, with systems of degree one exactly the regular languages can be generated, whereas with systems of size one (and arbitrary degree) we even cannot obtain all regular languages. Moreover, we establish corresponding results when considering linear membrane structures as objects and using rules which put a membrane with label b around a linear membrane object with the outermost membrane labeled by a or else erase the outermost membrane labeled by b of a linear membrane object.