Closure properties of Watson-Crick grammars - Mohamad Zulkufli, Nurul Liyana; Turaev, Sherzod; Mohd Tamrin, Mohd Izzuddin; Messikh, Azeddin (American Institute of Physics, 2015)
In this paper, we define Watson-Crick context-free grammars, as an extension of Watson-Crick regular grammars and Watson-Crick linear grammars with context-free grammar rules. We show the relation of Watson-Crick (regular and linear) grammars to the sticker systems, and study some of the important closure properties of the Watson-Crick grammars. We establish that the Watson-Crick regular grammars are closed under almost all of the main closure operations, while the differences between other Watson-Crick grammars with their corresponding Chomsky grammars depend on the computational power of the Watson-Crick grammars which still need to be studied.