On rule synchronization in membrane computing

Read full text Summarise with VIRAT
Authors: Péter Battyányi
Cited by: 0
References: 16

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Abstract 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.

Fields of Study & Subjects

DNA and Biological Computing Computability Logic AI Algorithms Cellular Automata and Applications

Publication details

Journal / source
Journal of Membrane Computing
Volume
8
Issue
3
Pages
375–385
Publication date
28 March 2026
Language
EN