Skip to main content
Top

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.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadata
Title
Circular Post Machines and P Systems with Exo-insertion and Deletion
Authors
Artiom Alhazov
Alexander Krassovitskiy
Yurii Rogozhin
Copyright Year
2012
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-28024-5_7

Premium Partner