Language generating alphabetic flat splicing P systems

Pan, Linqiang and Song, Bosheng and Nagar, Atulya K. and Subramanian, K.G. (2017) Language generating alphabetic flat splicing P systems. Theoretical Computer Science. ISSN 0304-3975 (Accepted for Publication)

Language generating P Systems.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (236kB) | Preview


An operation on strings, called at splicing was introduced, inspired by a splicing operation on circular strings considered in the study of modelling of the recombinant behaviour of DNA molecules. A simple kind of at splicing, called alphabetic at splicing, allows insertion of a word with a specified start symbol and/or a specified end symbol, between two pre-determined symbols in a given
word. In this work, we consider a P system with only alphabetic at splicing rules as the evolution rules and strings of symbols as objects in its regions. We examine the language generative power of the resulting alphabetic at splicing P systems (AFS P systems, for short). In particular, we show that AFS P systems with two membranes are more powerful in generative power than AFS P systems with a single membrane. We also construct AFS P systems with at most three membranes to generate languages that do not belong to certain other language classes and show an application to generation of chain code pictures.

Item Type: Article
Keywords: Membrane computing, P system, Flat splicing, Chomsky hierarchy
Faculty / Department: Faculty of Science > Mathematics and Computer Science
Depositing User: Atulya Nagar
Date Deposited: 17 Mar 2017 11:04
Last Modified: 07 Jun 2018 00:15

Actions (login required)

View Item View Item