A programmable DNA automaton model for context-free grammers

Research output: Contribution to report/book/conference proceedingsIn-proceedings paper

Authors

  • Da Ruan
  • W.-G. Li
  • Y.-S Ding
  • Z.-D. Huang
  • S.-H. Shao

Institutes & Expert groups

Documents & links

Abstract

Context-free grammars (CFGs) are widely applied in character string modeling. The languages accepted by CFGs are also accepted by pushdown automaton (PDA), and vice verse. Taking palindrome language as an example, we propose a novel method to construct a programmable DNA-based PDA, which is equivalent with the CFGs. We give out the nucleotides encoding for input alphabets, stack alphabets, the detectors to report the final result of PDA, and the transition rules. The major features of our method are demonstrated as follows: (1) to encode the components of PDA, we use general linear double-strands DNA (dsDNA) but not circular dsDNA; (2) we only use one restriction enzyme (FokI), that is employed for not only the transiting to state but also the operating to stack.

Details

Original languageEnglish
Title of host publicationProceedings of JCIS 2005
Place of PublicationSalt Lake City, Utah, United States
Pages1400-1403
Volume3
Publication statusPublished - Jul 2005
EventICIS 2005 - The 8th Joint Conference on Information Sciences - Salt Lake City, Utah, United States
Duration: 21 Jul 200526 Jul 2005

Conference

ConferenceICIS 2005 - The 8th Joint Conference on Information Sciences
CountryUnited States
CitySalt Lake City, Utah
Period2005-07-212005-07-26

Keywords

  • DNA computing model, programmable, context-free grammars

ID: 365266