Abstract
Splitting/fusion grammars were recently introduced as devices for the generation of hypergraph languages. Their rule application mechanism is inspired by basic operations of DNA computing. In this paper, we demonstrate that splitting/fusion grammars and well-known computational approaches based on DNA computing are closely related on a technical level beyond the mere motivation. This includes Adleman’s seminal experiment, insertion-deletion systems, and extended iterated 2-splicing systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266, 1021–1024 (1994)
Kreowski, H.-J., Kuske, S., Lye, A.: Fusion grammars: A novel approach to the generation of graph languages. In: de Lara, J., Plump, D. (eds.) ICGT 2017. LNCS, vol. 10373, pp. 90–105. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61470-0_6
Kreowski, H.-J., Kuske, S., Lye, A.: Splicing/fusion grammars and their relation to hypergraph grammars. In: Lambers, L., Weber, J. (eds.) ICGT 2018. LNCS, vol. 10887, pp. 3–19. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92991-0_1
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing—New Computing Paradigms. Springer, Heidelberg (1998)
Kreowski, H.-J., Klempien-Hinrichs, R., Kuske, S.: Some essentials of graph transformation. In: Ésik, Z., Martín-Vide, C., Mitrana, V. (eds.) Recent Advances in Formal Languages and Applications. Studies in Computational Intelligence, vol. 25, pp. 229–254. Springer, Heidelberg (2006). https://doi.org/10.1007/978-3-540-33461-3_9
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, London (1979)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85–103. Plenum Press, New York (1972)
Kari, L., Thierrin, G.: Contextual insertions/deletions and computability. Inf. Comput. 131(1), 47–61 (1996)
Kreowski, H.-J., Kuske, S.: Graph multiset transformation as a framework for massively parallel computation. In: Ehrig, H., Heckel, R., Rozenberg, G., Taentzer, G. (eds.) ICGT 2008. LNCS, vol. 5214, pp. 351–365. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87405-8_24
Acknowledgment
We are grateful to the anonymous reviewers for their critical comments that encouraged us to add some more explanations.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Kreowski, HJ., Kuske, S., Lye, A. (2019). Relating DNA Computing and Splitting/Fusion Grammars. In: Guerra, E., Orejas, F. (eds) Graph Transformation. ICGT 2019. Lecture Notes in Computer Science(), vol 11629. Springer, Cham. https://doi.org/10.1007/978-3-030-23611-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-23611-3_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-23610-6
Online ISBN: 978-3-030-23611-3
eBook Packages: Computer ScienceComputer Science (R0)