3.8 Article

Shallow laconic P systems can count

Journal

JOURNAL OF MEMBRANE COMPUTING
Volume 2, Issue 1, Pages 49-58

Publisher

SPRINGERNATURE
DOI: 10.1007/s41965-020-00032-4

Keywords

Shallow P systems; Laconic P systems; Send-in rules; Counting

Ask authors/readers for more resources

Uniform families of shallow P systems with active membranes and charges are known to characterize the complexity class P#P, since this kind of P systems are able to count the number of objects sent out by the dividing membranes. Such a power is absent in monodirectional systems, where no send-in rules are allowed: in this case, only languages in PNP can be recognized. Here, we show that even a tiny amount of communication (namely, allowing only a single send-in per membrane during the computation) is sufficient to achieve the ability to count and solve all problems in the class P#P, where all queries are performed independently.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

3.8
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available