Computational properties of Watson-Crick context-free grammars
Deoxyribonucleic acid, or popularly known as DNA, continues to inspire many theoretical computing models, such as sticker systems and Watson-Crick grammars. Sticker systems are the abstraction of ligation processes performed on DNA, while Watson-Crick grammars are models motivated from Watson-Crick...
| Main Authors: | , , , , |
|---|---|
| Format: | Proceeding Paper |
| Language: | English English |
| Published: |
The Institute of Electrical and Electronics Engineers, Inc.
2016
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/50833/ http://irep.iium.edu.my/50833/1/50833_Computational_Properties_of_Watson-Crick1.pdf http://irep.iium.edu.my/50833/4/50833_Computational%20Properties_scopus.pdf |
| _version_ | 1848783732987658240 |
|---|---|
| author | Mohamad Zulkufli, Nurul Liyana Turaev, Sherzod Mohd Tamrin, Mohd Izzuddin Az Eddine, Messikh Alshaikhli, Imad Fakhri Taha |
| author_facet | Mohamad Zulkufli, Nurul Liyana Turaev, Sherzod Mohd Tamrin, Mohd Izzuddin Az Eddine, Messikh Alshaikhli, Imad Fakhri Taha |
| author_sort | Mohamad Zulkufli, Nurul Liyana |
| building | IIUM Repository |
| collection | Online Access |
| description | Deoxyribonucleic acid, or popularly known as DNA, continues to inspire many theoretical computing models, such as sticker systems and Watson-Crick grammars. Sticker systems are the abstraction of ligation processes performed on DNA, while Watson-Crick grammars are models motivated from Watson-Crick finite automata and Chomsky grammars. Both of these theoretical models benefit from the Watson-Crick complementarity rule. In this paper, we establish the results on the relationship between Watson-Crick linear grammars, which is included in Watson-Crick context-free grammars, and sticker systems. We show that the family of arbitrary sticker languages, generated from arbitrary sticker systems, is included in the family of Watson-Crick linear languages, generated from Watson-Crick linear grammars. |
| first_indexed | 2025-11-14T16:26:02Z |
| format | Proceeding Paper |
| id | iium-50833 |
| institution | International Islamic University Malaysia |
| institution_category | Local University |
| language | English English |
| last_indexed | 2025-11-14T16:26:02Z |
| publishDate | 2016 |
| publisher | The Institute of Electrical and Electronics Engineers, Inc. |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | iium-508332017-04-21T07:34:42Z http://irep.iium.edu.my/50833/ Computational properties of Watson-Crick context-free grammars Mohamad Zulkufli, Nurul Liyana Turaev, Sherzod Mohd Tamrin, Mohd Izzuddin Az Eddine, Messikh Alshaikhli, Imad Fakhri Taha QA75 Electronic computers. Computer science Deoxyribonucleic acid, or popularly known as DNA, continues to inspire many theoretical computing models, such as sticker systems and Watson-Crick grammars. Sticker systems are the abstraction of ligation processes performed on DNA, while Watson-Crick grammars are models motivated from Watson-Crick finite automata and Chomsky grammars. Both of these theoretical models benefit from the Watson-Crick complementarity rule. In this paper, we establish the results on the relationship between Watson-Crick linear grammars, which is included in Watson-Crick context-free grammars, and sticker systems. We show that the family of arbitrary sticker languages, generated from arbitrary sticker systems, is included in the family of Watson-Crick linear languages, generated from Watson-Crick linear grammars. The Institute of Electrical and Electronics Engineers, Inc. 2016 Proceeding Paper PeerReviewed application/pdf en http://irep.iium.edu.my/50833/1/50833_Computational_Properties_of_Watson-Crick1.pdf application/pdf en http://irep.iium.edu.my/50833/4/50833_Computational%20Properties_scopus.pdf Mohamad Zulkufli, Nurul Liyana and Turaev, Sherzod and Mohd Tamrin, Mohd Izzuddin and Az Eddine, Messikh and Alshaikhli, Imad Fakhri Taha (2016) Computational properties of Watson-Crick context-free grammars. In: 2015 4th International Conference on Advanced Computer Science Applications and Technologies (ACSAT 2015), 8th-10th Dec. 2015, Kuala Lumpur. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7478741&filter%3DAND%28p_IS_Number%3A7478698%29%26pageNumber%3D2 10.1109/ACSAT.2015.19 |
| spellingShingle | QA75 Electronic computers. Computer science Mohamad Zulkufli, Nurul Liyana Turaev, Sherzod Mohd Tamrin, Mohd Izzuddin Az Eddine, Messikh Alshaikhli, Imad Fakhri Taha Computational properties of Watson-Crick context-free grammars |
| title | Computational properties of Watson-Crick context-free grammars |
| title_full | Computational properties of Watson-Crick context-free grammars |
| title_fullStr | Computational properties of Watson-Crick context-free grammars |
| title_full_unstemmed | Computational properties of Watson-Crick context-free grammars |
| title_short | Computational properties of Watson-Crick context-free grammars |
| title_sort | computational properties of watson-crick context-free grammars |
| topic | QA75 Electronic computers. Computer science |
| url | http://irep.iium.edu.my/50833/ http://irep.iium.edu.my/50833/ http://irep.iium.edu.my/50833/ http://irep.iium.edu.my/50833/1/50833_Computational_Properties_of_Watson-Crick1.pdf http://irep.iium.edu.my/50833/4/50833_Computational%20Properties_scopus.pdf |