On the power of deterministic and sequential communicating P systems

Luděk Cienciala, Lucie Ciencialová, Pierluigi Frisco, Petr Sosík

Research output: Contribution to journalArticle

Abstract

We characterize the computational power of several restricted variants of communicating P systems. We show that 2-deterministic communicating P systems with 2 membranes, working in either minimally or maximally parallel mode, are computationally universal. Considering the sequential mode, 2 membranes are shown to characterize the power of partially blind multicounter machines. Next, a characterization of the power of 1-deterministic communicating P systems is given. Finally, we show that the nondeterministic variant in maximally parallel mode is universal already with 1 membrane. These results demonstrate differences in computational power between nondeterminism, 2-determinism and 1-determinism, on one hand, and between sequential, minimally and maximally parallel modes, on the other hand. © World Scientific Publishing Company.

Original languageEnglish
Pages (from-to)415-431
Number of pages17
JournalInternational Journal of Foundations of Computer Science
Volume18
Issue number2
DOIs
Publication statusPublished - Apr 2007

Fingerprint Dive into the research topics of 'On the power of deterministic and sequential communicating P systems'. Together they form a unique fingerprint.

  • Cite this