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 (The Institute of Electrical and Electronics Engineers, Inc., 2016)
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.