<p>In this paper, we consider membrane system-like computational models equipped with a synchronization mechanism for rules. The synchronization mechanism means that, in addition to the usual set of rules, a set of finite tuples of membrane rules is specified. These tuples indicate which rule executions are linked, according to the constraints imposed by the various execution modes. We examine these models considering different rule semantics, or execution modes. We consider four types of execution modes, distinguishing between weak and strong modes, each defined with or without object reuse. The weak execution modes are likely less powerful than general Turing machines, and we demonstrate this for one specific case, while the other case remains a conjecture. Furthermore, we prove that in the strong execution mode, when additional conditions are imposed on synchronized rules compared to the weak execution modes, these models achieve computational completeness even without maximal parallelism. Finally, we demonstrate why these systems, when restricted to non-cooperative rules, cannot achieve computational completeness, even in the strong modesx.</p>

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

On rule synchronization in membrane computing

  • Péter Battyányi

摘要

In this paper, we consider membrane system-like computational models equipped with a synchronization mechanism for rules. The synchronization mechanism means that, in addition to the usual set of rules, a set of finite tuples of membrane rules is specified. These tuples indicate which rule executions are linked, according to the constraints imposed by the various execution modes. We examine these models considering different rule semantics, or execution modes. We consider four types of execution modes, distinguishing between weak and strong modes, each defined with or without object reuse. The weak execution modes are likely less powerful than general Turing machines, and we demonstrate this for one specific case, while the other case remains a conjecture. Furthermore, we prove that in the strong execution mode, when additional conditions are imposed on synchronized rules compared to the weak execution modes, these models achieve computational completeness even without maximal parallelism. Finally, we demonstrate why these systems, when restricted to non-cooperative rules, cannot achieve computational completeness, even in the strong modesx.