×

zbMATH — the first resource for mathematics

Universality in molecular and cellular computing. (English) Zbl 06496607
Beckmann, Arnold (ed.) et al., Evolving computability. 11th conference on computability in Europe, CiE 2015, Bucharest, Romania, June 29 – July 3, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-20027-9/pbk; 978-3-319-20028-6/ebook). Lecture Notes in Computer Science 9136, 95-104 (2015).
Summary: In this article we present an overview of the study of the universality problem in the area of molecular and cellular computing. We consider the results that deal explicitly with this problem and that aim to optimize the obtained construction. A particular attention is given to models based on the splicing operation as well as to multiset-rewriting based models.
For the entire collection see [Zbl 1314.68011].
MSC:
68Qxx Theory of computing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alhazov, A., Kogler, M., Margenstern, M., Rogozhin, Y., Verlan, S.: Small universal TVDH and test tube systems. Int. J. Found. Comput. Sci. 22(1), 143-154 (2011) · Zbl 1213.68271 · doi:10.1142/S0129054111007903
[2] Alhazov, A., Martín-Vide, C., Truthe, B., Dassow, J., Rogozhin, Y.: On networks of evolutionary processors with nodes of two types. Fundamenta Informaticae 91(1), 1-15 (2009) · Zbl 1193.68023
[3] Alhazov, A., Rogozhin, Y., Verlan, S.: On small universal splicing systems. Int. J. Found. Comput. Sci. 23(07), 1423-1438 (2012) · Zbl 1386.68059 · doi:10.1142/S0129054112400564
[4] Alhazov, A., Verlan, S.: Minimization strategies for maximally parallel multiset rewriting systems. Theor. Comput. Sci. 412(17), 1581-1591 (2011) · Zbl 1209.68284 · doi:10.1016/j.tcs.2010.10.033
[5] Barzdin, I.M.: On a class of turing machines (Minsky machines). Algebra i Logika 1, 42-51 (1963). (in Russian)
[6] Bonnet, R.: The reachability problem for vector addition system with one zero-test. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 145-157. Springer, Heidelberg (2011) · Zbl 1343.68160 · doi:10.1007/978-3-642-22993-0_16
[7] Castellanos, J., Martín-Vide, C., Mitrana, V., Sempere, J.M.: Solving NP-complete problems with networks of evolutionary processors. In: Mira, J., Prieto, A.G. (eds.) IWANN 2001. LNCS, vol. 2084, pp. 621-628. Springer, Heidelberg (2001) · Zbl 0982.68767 · doi:10.1007/3-540-45720-8_74
[8] Csuhaj-Varjú, E., Kari, L., Păun, G.: Test tube distributed systems based on splicing. Comput. Artif. Intell. 15(2-3), 211-232 (1996) · Zbl 0852.68051
[9] Dassow, J., Manea, F.: Accepting hybrid networks of evolutionary processors with special topologies and small communication. In: Proceedings of DCFS 2010, of EPTCS, vol. 31, pp. 68-77 (2010)
[10] Dassow, J., Manea, F., Truthe, B.: On the power of accepting networks of evolutionary processors with special topologies and random context filters. Fundamenta Informaticae 136(1-2), 1-35 (2015) · Zbl 1335.68089
[11] Dassow, J., Mitrana, V.: Accepting networks of non-inserting evolutionary processors. In: Priami, C., Back, R.-J., Petre, I. (eds.) Transactions on Computational Systems Biology XI. LNCS, vol. 5750, pp. 187-199. Springer, Heidelberg (2009) · Zbl 1230.68127 · doi:10.1007/978-3-642-04186-0_9
[12] Demaine, E.D., Demaine, M.L., Fekete, S.P., Patitz, M.J., Schweller, R.T., Winslow, A., Woods, D.: One tile to rule them all: simulating any tile assembly system with a single universal tile. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 368-379. Springer, Heidelberg (2014) · Zbl 1410.68123
[13] Doty, D., Lutz, J.H., Patitz, M.J., Schweller, R.T., Summers, S.M., Woods, D.: The tile assembly model is intrinsically universal. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pp. 302-310 (2012)
[14] Freund, R., Oswald, M.: A small universal antiport P system with forbidden context. In: Leung, H., Pighizzini, G. (eds.) 8th International Workshop on Descriptional Complexity of Formal Systems, pp. 259-266. Proceedings, New Mexico (2006)
[15] Freund, R., Verlan, S.: A formal framework for static (Tissue) P systems. In: Eleftherakis, G., Kefalas, P., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2007. LNCS, vol. 4860, pp. 271-284. Springer, Heidelberg (2007) · Zbl 1137.68387 · doi:10.1007/978-3-540-77312-2_17
[16] Frisco, P.: Direct constructions of universal extended H systems. Theor. Comput. Sci. 296(2), 269-293 (2003) · Zbl 1044.68057 · doi:10.1016/S0304-3975(02)00658-8
[17] Frisco, P., Hoogeboom, H.J., Sant, P.: A direct construction of a universal P system. Fundamenta Informaticae 49(1-3), 103-122 (2002) · Zbl 0997.68053
[18] Head, T.: Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors. Bull. Math. Biol. 49(6), 737-759 (1987) · Zbl 0655.92008 · doi:10.1007/BF02481771
[19] Head, T.: Splicing languages generated with one sided context. In: Paun, G. (ed.) Computing with Bio-Molecules. Theory and Experiments, pp. 158-181. Springer, Singapore (1998)
[20] Hopcroft, J., Pansiot, J.-J.: On the reachability problem for 5-dimensional vector addition systems. Theor. Comput. Sci. 8(2), 135-159 (1979) · Zbl 0466.68048 · doi:10.1016/0304-3975(79)90041-0
[21] Ivanov, S., Pelz, E., Verlan, S.: Small universal Petri nets with inhibitor arcs (2013). arXiv, CoRR. · Zbl 1416.68122
[22] Ivanov, S., Pelz, E., Verlan, S.: Small universal non-deterministic Petri nets with inhibitor arcs. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 186-197. Springer, Heidelberg (2014) · Zbl 1416.68122
[23] Ivanov, S., Rogozhin, Y., Verlan, S.: Small universal networks of evolutionary processors. J. Autom. Lang. Comb. 19(1—4), 133-144 (2014) · Zbl 1355.68090
[24] Kari, L.: DNA computing: arrival of biological mathematics. Math. Intell. 19(2), 9-22 (1997) · Zbl 0942.68562 · doi:10.1007/BF03024425
[25] Kim, J., White, K.S., Winfree, E.: Construction of an in vitro bistable circuit from synthetic transcriptional switches. Mol. Syst. Biol. 2, 68 (2006) · doi:10.1038/msb4100099
[26] Korec, I.: Small universal register machines. Theor. Comput. Sci. 168(2), 267-301 (1996) · Zbl 0874.68105 · doi:10.1016/S0304-3975(96)00080-1
[27] Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Further results on insertion-deletion systems with one-sided contexts. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 333-344. Springer, Heidelberg (2008) · Zbl 1156.68458 · doi:10.1007/978-3-540-88282-4_31
[28] Lathrop, J.I., Lutz, J.H., Patitz, M.J., Summers, S.M.: Computability and complexity in self-assembly. Theory Comput. Syst. 48(3), 617-647 (2011) · Zbl 1217.68095 · doi:10.1007/s00224-010-9252-0
[29] Loos, R., Manea, F., Mitrana, V.: On small, reduced, and fast universal accepting networks of splicing processors. Theor. Comp. Sci. 410(45), 406-416 (2009) · Zbl 1160.68014 · doi:10.1016/j.tcs.2008.09.048
[30] Malcev, A.I.: Algorithms and Recursive Functions. Wolters-Noordhoff, Groningen (1970)
[31] Manea, F., Martín-Vide, C., Mitrana, V.: On the size complexity of universal accepting hybrid networks of evolutionary processors. Math. Struct. Comput. Sci. 8, 17:753-771 (2007) · Zbl 1125.68053
[32] Manea, F., Martín-Vide, C., Mitrana, V.: Accepting Networks of Evolutionary Word and Picture Processors: A Survey, pp. 525-561. Imperial College Press, London (2010). Chap. 10 · Zbl 1230.68072
[33] Margenstern, M.: Frontier between decidability and undecidability: a survey. Theor. Comput. Sci. 231(2), 217-251 (2000) · Zbl 0956.03041 · doi:10.1016/S0304-3975(99)00102-4
[34] Margenstern, M., Rogozhin, Y.: Time-varying distributed H systems of degree 1 generate all recursively enumerable languages. In: Ito, M., Păun, G., Yu, S. (eds.) Words, Semigroups, and Transductions, pp. 329-339. World Scientific, Singapore (2001) · Zbl 1013.68111 · doi:10.1142/9789812810908_0025
[35] Margenstern, M., Rogozhin, Y., Verlan, S.: Time-varying distributed H systems with parallel computations: the problem is solved. In: Chen, J., Reif, J.H. (eds.) DNA 2003. LNCS, vol. 2943, pp. 48-53. Springer, Heidelberg (2004) · Zbl 1098.68044 · doi:10.1007/978-3-540-24628-2_6
[36] Matveevici, A., Rogozhin, Y., Verlan, S.: Insertion-deletion systems with one-sided contexts. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 205-217. Springer, Heidelberg (2007) · Zbl 1155.68419 · doi:10.1007/978-3-540-74593-8_18
[37] Minsky, M.: Size and structure of universal Turing machines using tag systems. In: Recursive Function Theory: Proceedings, Symposium in Pure Mathematics, vo. 5, pp. 229-238. Provelence (1962) · Zbl 0192.06601
[38] Minsky, M.: Computations: Finite and Infinite Machines. Prentice Hall, USA (1967) · Zbl 0195.02402
[39] Neary, T., Woods, D.: The complexity of small universal turing machines: a survey. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 385-405. Springer, Heidelberg (2012) · Zbl 1302.68117 · doi:10.1007/978-3-642-27660-6_32
[40] Ollinger, N.: Automates cellulaires: structures. Ph.D. thesis, ENS Lyon (2002)
[41] Ollinger, N.: The quest for small universal cellular automata. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 318-329. Springer, Heidelberg (2002) · doi:10.1007/3-540-45465-9_28
[42] Patil, S.S.: Coordination of asynchronous events. Ph.D. thesis, MIT (1970)
[43] Patitz, M.J., Summers, S.M.: Self-assembly of decidable sets. In: Calude, C.S., Costa, J.F., Freund, R., Oswald, M., Rozenberg, G. (eds.) UC 2008. LNCS, vol. 5204, pp. 206-219. Springer, Heidelberg (2008) · Zbl 1166.68329
[44] Păun, G.: Computing with membranes. J. Comput. Syst. Sci. 1(61), 108-143 (2000). Also TUCS Report No. 208, 1998 · Zbl 0956.68055 · doi:10.1006/jcss.1999.1693
[45] Păun, G.: Membrane Computing: An Introduction. Springer, Heidelberg (2002) · doi:10.1007/978-3-642-56196-2
[46] Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, Heidelberg (1998) · Zbl 0940.68053 · doi:10.1007/978-3-662-03563-4
[47] Păun, G., Rozenberg, G., Salomaa, A.: The Oxford Handbook Of Membrane Computing. Oxford University Press, New York (2009)
[48] Qian, L., Soloveichik, D., Winfree, E.: Efficient turing-universal computation with DNA polymers. In: Sakakibara, Y., Mi, Y. (eds.) DNA 16 2010. LNCS, vol. 6518, pp. 123-140. Springer, Heidelberg (2011) · Zbl 1309.68071 · doi:10.1007/978-3-642-18305-8_12
[49] Rogozhin, Y.: Small universal turing machines. Theor. Comput. Sci. 168(2), 215-240 (1996) · Zbl 0874.68106 · doi:10.1016/S0304-3975(96)00077-1
[50] Rozenberg, G., Bäck, T., Kok, J.N. (eds.): Handbook of Natural Computing. Springer, Heidelberg (2012) · Zbl 1248.68001
[51] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages. Springer, Heidelberg (1997) · Zbl 0866.68057 · doi:10.1007/978-3-662-07675-0
[52] Schroeppel, R.: A two counter machine cannot calculate 2N. AI Memos, Cambridge (1972)
[53] Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314(5805), 1585-1588 (2006) · doi:10.1126/science.1132493
[54] Shannon, C.E.: A universal Turing machine with two internal states. Autom. Stud. Ann. Math. Stud. 34, 157-165 (1956)
[55] Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. SIAM J. Comput. 36(6), 1544-1569 (2007) · Zbl 1136.68029 · doi:10.1137/S0097539704446712
[56] Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 42(2), 230-265 (1936) · Zbl 0016.09701
[57] Verlan, S.: Study of language-theoretic computational paradigms inspired by biology. Habilitation thesis, Université Paris Est (2010)
[58] von Neumann, J.: Theory of self-reproducing automata. University of Illinois (1966)
[59] Watanabe, S.: 5-symbol 8-state and 5-symbol 6-state universal turing machines. J. ACM 8(4), 476-483 (1961) · Zbl 0154.41605 · doi:10.1145/321088.321090
[60] Winfree, E.: Algorithmic self-assembly of DNA. Ph.D. thesis, Caltech (1998)
[61] Wolfram, S.: A New Kind of Science. Wolfram Media Inc., UK (2002) · Zbl 1022.68084
[62] Zizza, R.: Splicing systems. Scholarpedia 5(7), 9397 (2010) · Zbl 1208.68133 · doi:10.4249/scholarpedia.9397
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.