Universality of Splicing Test Tube Systems with Two Tubes

• Autorzy: Verlan S. , Margenstern M.
• Języki publikacji: EN

Abstrakty

EN

Splicing test tube systems are one of the first distributed computing models based on splicing. The model introduces (test) tubes where the splicing operation is applied, which are arranged in a communication network with filters that permits to redistribute the words between the tubes at each step. We show that the computational completeness can be achieved with two tubes when the communication graph does not have self-loops. We also construct a universal splicing test tube system with 2 tubes having 23 rules.

Słowa kluczowe

EN

splicing; test tube systems; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 329--342
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Verlan S.

autor

Margenstern M.

• LACL, Université Paris Est, 61, av. Gén. de Gaulle, 94010, Créteil, France,

Bibliografia

• [1] Adleman, L.: On constructing a molecular computer, in: DNA-based computers (R. Lipton, E.Baum, Eds.), vol. 27 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AmericanMathematical Society, 1996, 1-21.
• [2] Alhazov, A., Kogler, M., Margenstern, M., Rogozhin, Y., Verlan, S.: Small Universal TVDH and Test Tube Systems, Int. J. Found. Comput. Sci., 22(1), 2011, 143-154.
• [3] Alhazov, A., Rogozhin, Y., Verlan, S.: A Small Universal Splicing P System, in: Membrane Computing - 11th International Conference, CMC 2010, Jena, Germany, August 24-27, 2010. Revised Selected Papers (M. Gheorghe, T. Hinze, G. Paun, G. Rozenberg, A. Salomaa, Eds.), vol. 6501 of Lecture Notes in Computer Science, Springer, 2010, 95-102.
• [4] Cocke, J., Minsky,M.: Universality of tag systems with P=2, Journal of the ACM, 11(1), 1964, 15-20.
• [5] Csuhaj-Varj´u, E., Kari, L., Pǎun, G.: Test Tube Distributed Systems Based on Splicing, Computers and AI, 15(2-3), 1996, 211-232.
• [6] Csuhaj-Varj´u, E., Verlan, S.: On Length-Separating Test Tube Systems, Natural Computing, 7(2), 2008, 167-181.
• [7] Freund, F., Freund, R.: Test tube systems with controlled applications of rules, in: Proceedings of IEEE International Conference on Evolutionary Computation, Indianapolis, IN , USA, 1997, 237-242.
• [8] Freund, F., Freund, R., Oswald, M.: Splicing Test Tube Systems and Their Relation to Splicing Membrane Systems, in: Aspects of Molecular Computing, Essays Dedicated to Tom Head on the Occasion of His 70th Birthday (N. Jonoska, G. Paun, G. Rozenberg, Eds.), vol. 2950 of Lecture Notes in Computer Science, Springer, 2004, 139-151.
• [9] Freund, R., Freund, F.: Test tube systems: when two tubes are enough, in: Developments in Language Theory, Foundations, Applications, and Perspectives, Aachen, Germany, 6-9 July 1999 (G. Rozenberg, W. Thomas, Eds.), World Scientific, 1999, 338-350.
• [10] Frisco, P., Zandron, C.: On variants of communicating distributed H systems, Fundamenta Informaticae, 48(1), October 2001, 9-20.
• [11] Head, T.: Formal Language Theory and DNA: an Analysis of the Generative Capacity of Specific Recombinant Behaviors., Bulletin of Mathematical Biology, 49(6), 1987, 737-759.
• [12] Head, T., Pǎun, G., Pixton, D.: Language theory and molecular genetics. Generative mechanisms suggested by DNA recombination, in: Handbook of Formal Languages, 3 volumes [20], 295-360.
• [13] Minsky, M.: Computations: Finite and Infinite Machines, Prentice Hall, Englewood Cliffts, NJ, 1967.
• [14] Post, E.: Formal reductions of the general combinatorial decision problem, American Journal of Mathematics, 65(2), 1943, 197-215.
• [15] Priese, L., Rogozhin, Y., Margenstern, M.: Finite H-Systems with 3 Test Tubes are not Predictable, in: Proceedings of Pacific Symposium on Biocomputing (R. Altman, A. Dunker, L. Hanter, T. Klein, Eds.), World Scientific Publishing, Singapore, 1998, 545-556.
• [16] Pǎun, G.: Membrane Computing. An Introduction, Springer Verlag, Berlin, Heidelberg, New York, 2002.
• [17] Pǎun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms, Springer Verlag, Berlin, Heidelberg, New York, September 1998.
• [18] Pǎun, G., Yokomori, T.: Membrane Computing Based on Splicing, in: DNA Based Computers (E. Winfree, D. Gifford, Eds.), vol. 54 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1999, 217-232.
• [19] Rogozhin, Y., Verlan, S.: On the Rule Complexity of Universal Tissue P Systems, in: Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers (R. Freund, G. Paun, G. Rozenberg, A. Salomaa, Eds.), vol. 3850 of Lecture Notes in Computer Science, Springer, 2005, 356-362.
• [20] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, 3 volumes, Springer Verlag, Berlin, Heidelberg, New York, 1997.
• [21] Verlan, S.: Communicating Distributed H Systems with Alternating Filters, in: Aspects of Molecular Computing. Essays Dedicated to Tom Head on the Occasion of His 70th Birthday (N. Jonoska, G. Paun, G. Rozenberg, Eds.), vol. 2950 of Lecture Notes in Computer Science, Springer Verlag, Berlin, Heidelberg, New York, 2004, 367-384.
• [22] Verlan, S.: Head Systems and Applications to Bioinformatics, Ph.D. Thesis, University of Metz, 2004.
• [23] Verlan, S.: A Boundary Result on Enhanced Time-Varying Distributed H Systems with Parallel Computations, Theoretical Computer Science, 344(2-3), 2005, 226-242, ISSN 0304-3975