loading...
On Symport/Antiport P Systems with One or Two Symbols
Timisoara, Romania September 25-September 29
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SYNASC.2005.52Seventh International Symposium on Sy ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Oscar H. Ibarra, University of California at Santa Barbara
Sara Woodworth, University of California at Santa Barbara
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.