The Relations among Watson-Crick Automata and Their Relations with Context-Free Languages

• Okawa, Satoshi

• Hirose, Sadaki

抄録

application/pdf

Watson-Crick automata were introduced as a new computer model and have been intensively investigated regarding their computational power. In this paper, aiming to establish the relations among language families defined by Watson-Crick automata and the family of context-free languages completely, we obtain the following results. (1) F1WK=FSWK=FWK, (2) FWK=AWK, (3) there exists a language which is not context-free but belongs to NWK, and (4) there exists a context-free language which does not belong to AWK.

Article

IEICE transactions on information and systems E89-D(10), Page 2591-2599

収録刊行物

• IEICE transactions on information and systems

  IEICE transactions on information and systems 89 (10), 2591-2599, 2006-10

  電子情報通信学会

キーワード

• DNA computer
• Watson-Crick automata
• formal languages
• language family

詳細情報

• CRID: 1050564289054772992
• NII論文ID: 110007538463
• NII書誌ID: AA10826272
• ISSN: 09168532
• HANDLE: 10110/5699
• Web Site: https://toyama.repo.nii.ac.jp/records/3422
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles