Closure properties of Watson-Crick grammars

Nurul Liyana Binti Mohamad Zulkufli, Sherzod Turaev, Mohd Izzuddin Mohd Tamrin, Messikh Azeddine

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationInnovation and Analytics Conference and Exhibition, IACE 2015
Subtitle of host publicationProceedings of the 2nd Innovation and Analytics Conference and Exhibition
EditorsNazihah Ahmad, Jafri Zulkepli, Adyda Ibrahim, Nazrina Aziz, Syariza Abdul-Rahman
PublisherAmerican Institute of Physics Inc.
ISBN (Electronic)9780735413382
Publication statusPublished - Dec 11 2015
Externally publishedYes
Event2nd Innovation and Analytics Conference and Exhibition, IACE 2015 - Alor Setar, Kedah, Malaysia
Duration: Sept 29 2015Oct 1 2015

Publication series

NameAIP Conference Proceedings
ISSN (Print)0094-243X
ISSN (Electronic)1551-7616


Conference2nd Innovation and Analytics Conference and Exhibition, IACE 2015
CityAlor Setar, Kedah

ASJC Scopus subject areas

  • General Physics and Astronomy


Dive into the research topics of 'Closure properties of Watson-Crick grammars'. Together they form a unique fingerprint.

Cite this