On rule synchronization in membrane computing
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