Networks of splicing processors: simulations between topologies
Tóm tắt
Networks of splicing processors are one of the theoretical computational models that take inspiration from nature to efficiently solve problems that our current computational knowledge is not able to. One of the issues restricting/hindering is practical implementation is the arbitrariness of the underlying graph, since our computational systems usually conform to a predefined topology. We propose simulations of networks of splicing processors having arbitrary underlying graphs by networks whose underlying graphs are of a predefined topology: complete, star, and grid graphs. We show that all of these simulations are time efficient in the meaning that they preserve the time complexity of the original network: each computational step in that network is simulated by a fixed number of computational steps in the new topologic networks. Moreover, these simulations do not modify the order of magnitude of the network size.
Tài liệu tham khảo
Arroyo, F., Castellanos, J., Dassow, J., Mitrana, V., & Sanchez-Couso, J. R. (2013). Accepting splicing systems with permitting and forbidding words. Acta Inf., 50, 1–14. https://doi.org/10.1007/s00236-012-0169-8
Bordihn, H., Mitrana, V., Păun, A., Păun, M. (2017). Networks of polarized splicing processors. In Theory and Practice of Natural Computing, TPNC 2017, Lecture Notes in Computer Science 10687, 165–177. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-319-71069-3_13
Bordihn, H., Mitrana, V., Negru, M. C., Păun, A., & Păun, M. (2018). Small networks of polarized splicing processors are universal. Natural Computing, 17, 799–809. https://doi.org/10.1007/s11047-018-9691-0
Castellanos, J., Mitrana, V., & Santos, E. (2011). Splicing systems: accepting versus generating. In Models of Computation in Context. CiE 2011, Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 6735, 41–50. https://doi.org/10.1007/978-3-642-21875-0_5
Head, T. (1987). Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviours. Bull. Math. Biol., 49, 737–759. https://doi.org/10.1007/BF02481771
Head, T., Păun, G., & Pixton, D. (1996). Language theory and molecular genetics: Generative mechanisms suggested by DNA recombination. In Handbook of Formal Languages, 2, 295–360. https://doi.org/10.1007/978-3-662-07675-0_7
Head, T. (2011). How the structure of DNA molecules provides tools for computation. In Biology, Computation and Linguistics. Frontiers in Artificial Intelligence and Applications vol. 228, 3–8. IOS Press. https://doi.org/10.3233/978-1-60750-762-8-3
Head, T. (2012). Restriction enzymes in language generation and plasmid computing In Biomolecular Information Processing: From Logic Systems to Smart Sensors and Actuators, 245–263. Wiley Online Library. https://doi.org/10.1002/9783527645480.CH13
Jonoska, N., Păun, G., Rozenberg, G. (Eds.) (2004). Aspects of Molecular Computing. Essays Dedicated to Tom Head on the Occasion of His 70th Birthday, Lecture Notes in Computer Science vol. 2950. Springer, Berlin, Heidelberg. https://doi.org/10.1007/b94864
Loos, R., Manea, F., & Mitrana, V. (2009). On small, reduced, and fast universal accepting networks of splicing processors. Theoretical Computer Science, 410, 406–416. https://doi.org/10.1016/j.tcs.2008.09.048
Manea, F., Martín-Vide, C., Mitrana, V. (2006). All NP-problems can be solved in polynomial time by accepting networks of splicing processors of constant size. In: DNA Computing. Lecture Notes in Computer Science, vol. 4287, 47–57. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11925903_4
Manea, F., Martín-Vide, C., & Mitrana, V. (2007). Accepting networks of splicing processors: complexity results. Theoretical Computer Science, 371, 72–82. https://doi.org/10.1016/j.tcs.2006.10.015
Mitrana, V., Petre, I., & Rogojin, V. (2010). Accepting splicing systems. Theoret. Comput. Sci., 411, 2414–2422. https://doi.org/10.1016/j.tcs.2010.03.025
Mitrana, V., Păun, A., & Păun, M. (2021). Non-preserving accepting splicing systems. Jounal Automata Languages Combinatorics, 26, 109–124. https://doi.org/10.25596/jalc-2021-109
Păun, G. (1996). On the splicing operation. Discrete Applied Mathematics, 70, 57–79. https://doi.org/10.1016/0166-218X(96)00101-1
Păun, G., Rozenberg, G., & Salomaa, A. (1998). DNA computing: New Computing Paradigms. Springer, Berlin, Heidelberg.https://doi.org/10.1007/3-540-48523-6_9
Rozenberg, G., & Salomaa, A. (1997). Handbook of Formal Languages. Springer, Berlin, Heidelberg.https://doi.org/10.1007/978-3-662-07675-0