2012 | OriginalPaper | Chapter
Circular Post Machines and P Systems with Exo-insertion and Deletion
Authors : Artiom Alhazov, Alexander Krassovitskiy, Yurii Rogozhin
Published in: Membrane Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper focuses on P systems with one-symbol insertion and deletion without contexts. The main aim of this paper is to consider the operations applied at the ends of the string, and prove the computational completeness in case of priority of deletion over insertion. This result presents interest since the strings are controlled by a tree structure only, and because insertion and deletion of one symbol are the simplest string operations.
To obtain a simple proof, we introduce here a new variant (CPM5) of circular Post machines (Turing machines moving one-way on a circular tape): those with instructions changing a state and either reading one symbol or writing one symbol. We believe CPM5 deserves attention as a simple, yet useful tool.
In the last part of the paper, we return to the case without priorities. We give a lower bound on the power of such systems, which holds even for one-sided operations only.