TY - GEN
T1 - Computational Properties of Watson-Crick Context-Free Grammars
AU - Zulkufli, Nurul Liyana Binti Mohamad
AU - Turaev, Sherzod
AU - Tamrin, Mohd Izzuddin Mohd
AU - Messikh, Azeddine
AU - Alshaikhli, Imad Fakhri Taha
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/5/25
Y1 - 2016/5/25
N2 - 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.
AB - 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.
KW - Watson-Crick automata
KW - Watson-Crick grammars
KW - formal grammars
KW - formal languages
KW - sticker systems
UR - http://www.scopus.com/inward/record.url?scp=84979009606&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979009606&partnerID=8YFLogxK
U2 - 10.1109/ACSAT.2015.19
DO - 10.1109/ACSAT.2015.19
M3 - Conference contribution
AN - SCOPUS:84979009606
T3 - Proceedings - 2015 4th International Conference on Advanced Computer Science Applications and Technologies, ACSAT 2015
SP - 186
EP - 191
BT - Proceedings - 2015 4th International Conference on Advanced Computer Science Applications and Technologies, ACSAT 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 4th International Conference on Advanced Computer Science Applications and Technologies, ACSAT 2015
Y2 - 8 December 2015 through 10 December 2015
ER -