Advertisement
Published in:
2006 | OriginalPaper | Chapter
On Symport/Antiport P Systems and Semilinear Sets
Authors : Oscar H. Ibarra, Sara Woodworth, Hsu-Chun Yen, Zhe Dang
Published in: Membrane Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We introduce some restricted models of symport/antiport P systems that are used as acceptors (respectively, generators) of sets of tuples of non-negative integers and show that they characterize precisely the semilinear sets. Specifically, we prove that a set
R
⊆ N
k
is accepted (respectively, generated) by a restricted system if and only if
R
is a semilinear set. We also show that “slight” extensions of the models will allow them to accept (respectively, generate) non-semilinear sets. In fact, for these extensions, the emptiness problem is undecidable.