Advertisement
Published in:
2017 | OriginalPaper | Chapter
Model Checking for Computation Tree Logic with Past Based on DNA Computing
Authors : Yingjie Han, Qinglei Zhou, Linfeng Jiao, Kai Nie, Chunyan Zhang, Weijun Zhu
Published in: Bio-inspired Computing: Theories and Applications
Publisher: Springer Singapore
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.