Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC'05) On Symport/Antiport P Systems with One or Two Symbols Timisoara, Romania September 25-September 29 ISBN: 0-7695-2453-2
We look at the computational power of symport/antiport system (SA) acceptors and generators with small numbers of membranes and objects. We show that even with a single object and only three membranes, a SA acceptor can accept the nonsemilinear set L = {2ⁿ∣n ≥ 0}. L can also be accepted with two objects and only one membrane. This latter model can accept all unary semilinear (i.e., regular) sets. We also show that for any k ≥ 1, the class of sets of k-tuples of nonnegative integers accepted by partially blind (multi-) counter machines is a subclass of the class of sets of k-tuples accepted by 1-object multi-membrane SA acceptors. Similarly, the class of sets of k-tuples of nonnegative integers generated by partially blind counter machines is a subclass of the class of sets of k-tuples generated by 1-object multi-membrane SA generators. As a corollary, the unary semilinear sets are a proper subclass of the unary sets of numbers accepted by SA acceptors with one object and 8 membranes. Whether or not 1-object multi-membrane SA acceptors (resp., generators) are universal remains an interesting open question.
Citation:
Oscar H. Ibarra, Sara Woodworth, "On Symport/Antiport P Systems with One or Two Symbols," synasc, pp.431-439, Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||