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

Membranes
Industry

Cite this

Cienciala, Luděk ; Ciencialová, Lucie ; Frisco, Pierluigi ; Sosík, Petr. / On the power of deterministic and sequential communicating P systems. In: International Journal of Foundations of Computer Science. 2007 ; Vol. 18, No. 2. pp. 415-431.
@article{236090d2fa2f411fa441a81b64f3cf79,
title = "On the power of deterministic and sequential communicating P systems",
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. {\circledC} World Scientific Publishing Company.",
author = "Luděk Cienciala and Lucie Ciencialov{\'a} and Pierluigi Frisco and Petr Sos{\'i}k",
year = "2007",
month = "4",
doi = "10.1142/S0129054107004759",
language = "English",
volume = "18",
pages = "415--431",
journal = "International Journal of Foundations of Computer Science.",
issn = "0129-0541",
publisher = "World Scientific Publishing",
number = "2",

}

On the power of deterministic and sequential communicating P systems. / Cienciala, Luděk; Ciencialová, Lucie; Frisco, Pierluigi; Sosík, Petr.

In: International Journal of Foundations of Computer Science, Vol. 18, No. 2, 04.2007, p. 415-431.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the power of deterministic and sequential communicating P systems

AU - Cienciala, Luděk

AU - Ciencialová, Lucie

AU - Frisco, Pierluigi

AU - Sosík, Petr

PY - 2007/4

Y1 - 2007/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34247188600&partnerID=8YFLogxK

U2 - 10.1142/S0129054107004759

DO - 10.1142/S0129054107004759

M3 - Article

VL - 18

SP - 415

EP - 431

JO - International Journal of Foundations of Computer Science.

JF - International Journal of Foundations of Computer Science.

SN - 0129-0541

IS - 2

ER -