Abstract
Deoxyribonucleic acid (DNA) computing provides a novel way of breaking through the limitations of traditional computation framework. Some complicated computational problems on small-scale have been solved. Model checking is a notable verification technique which is important to security-critical system. We employ DNA computing models and propose DNA algorithms for checking four elementary formulas of computation tree logic with past-time constructs in this paper. The model checking algorithms based on DNA computing are proved to be practicable and valid by simulations. The time complexity of the algorithms is reduced to linearity while the classical algorithm is PSPACE-complete. It indicates that a complexity computational problem is solved on DNA-computing based and the problems which can be solved by DNA computing are enriched. Meanwhile, it could be a benefit to diagnosis and treatment of genetic diseases at molecular level.
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
Zimmermann, K.H., Martínez-Pérez, I., Ignatova, Z.: DNA computing models. Springer, New York (2008)
Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266(5187), 1021–1023 (1994)
Lipton, R.J.: DNA solution of hard computational problems. Science 268(5210), 542–545 (1995)
Fan, Y.K., Qiang, X.L., Xu, J.: Sticker model for maximum clique problem and maximum in-dependent set. Chin. J. Comput. 33(2), 305–310 (2010)
Shi, X.L., Wang, Z.Y., Deng, C.Y., et al.: A novel bio-sensor based on DNA strand displacement. PLoS ONE 9(10), e108856 (2014)
Li, X., Song, T., Shi, X.L., et al.: A universal fast colorimetric method for DNA signal de-tection with DNA strand displacement and gold nanoparticles. J. Nanomater. 2015, 1–9 (2015)
Li, X., Li, H., Song, T., et al.: Highly biocompatible drug-delivery systems based on DNA nanotechnology. J. Biomed. Nanotechnol. (2017)
Shi, X.L., Chen, C.Z., Li, X., et al.: Size controllable DNA nanoribbons assembled from three types of reusable brick single-strand DNA tiles. Soft Matter 11(43), 8484–8492 (2015)
Shi, X.L., Wu, X.X., Song, T., et al.: Construction of DNA nanotubes with controllable diameters and patterns by using hierarchical DNA sub-tiles. Nanoscale 8(31), 14785–14792 (2016)
Clarke, E.M., Grumberg, O., Peled, D.A.: Model Checking. MIT Press, Cambridge (1999)
Emerson, E.A.: Using branching time temporal logic to synthesize synchronization skele-tons. Sci. Comput. Program. 2(3), 241–266 (1982)
Lichtenstein, O., Pnueli, A., Zuck, L.: The Glory of the Past. Logics of Programs. Springer, Heidelberg (1985)
Emerson, E.A.: Temporal and modal logic. In: Handbook of Theoretical Computer Science, vol. B, pp. 995–1072 (1990)
Emerson, E.A., Hager, K.D., Konieczka, J.H.: Molecular model checking. Int. J. Found. Comput. Sci. 17(04), 733–741 (2006)
Zhu, W.-J., Zhou, Q.-L., Li, Y.-L.: LTL model checking based on DNA computing. Acta Electron. Sin. 44(6), 1265–1271 (2016)
Han, Y.-J., Zhu, W.-J., Jiao, L.-F., et al.: DNA computing methods of LTL model checking on Xp. Mini-Micro Syst. 38(3), 553–558 (2017)
Kupferman, O., Pnueli, A.: Once and for all. In: IEEE Symposium on Logic in Computer Science, vol. 78, pp. 25–35 (1995)
Laroussinie, F., Schnoebelen, P.: A hierarchy of temporal logics with past. Theoret. Comput. Sci. 148(2), 303–324 (1995)
Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266(5187), 1021–1024 (1994)
Adleman, L.M.: On constructing a molecular computer. In: DIMACS, vol. 27, pp. 1–21 (2007)
NUPACK (2017). http://www.nupack.org/partition/new
Acknowledgments
This work was supported by the National Natural Science Foundation of China under Grant 61572444, U1204608, and China Postdoctoral Science Foundation under Grant 2015M572120, as well as Basic and Cutting-edge technology research projects of Henan Province Science and Technology Department under Grant 152300410055.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Han, Y., Zhou, Q., Jiao, L., Nie, K., Zhang, C., Zhu, W. (2017). Model Checking for Computation Tree Logic with Past Based on DNA Computing. In: He, C., Mo, H., Pan, L., Zhao, Y. (eds) Bio-inspired Computing: Theories and Applications. BIC-TA 2017. Communications in Computer and Information Science, vol 791. Springer, Singapore. https://doi.org/10.1007/978-981-10-7179-9_11
Download citation
DOI: https://doi.org/10.1007/978-981-10-7179-9_11
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-7178-2
Online ISBN: 978-981-10-7179-9
eBook Packages: Computer ScienceComputer Science (R0)