Lecture Notes in Computer Science, 2004, Volume 2933/2004, 163-192, DOI: 10.1007/978-3-540-24619-0_26

About Splicing P Systems with Immediate Communication and Non-extended Splicing P Systems

Sergey Verlan

View Related Documents

Abstract

We consider splicing P systems with immediate communication introduced by Gh. Păun in [5]. We solve the open problem Q17 from that book by proving that systems with two membranes can generate any recursively enumerable language. We discuss the similarities between splicing P systems with immediate communication having two membranes and time-varying distributed H systems with two components. We also consider non-extended splicing P systems, i.e., without a terminal alphabet. We show that it is possible to generate any recursively enumerable language by such systems with two membranes. In this way we solve the open problem Q16 from the same book.

Fulltext Preview

Image of the first page of the fulltext document