Watson–Crick context-free grammars: Grammar simpliﬁcations and a parsing algorithm - Mohamad Zulkufli, Nurul Liyana; Turaev, Sherzod; Mohd Tamrin, Mohd Izzuddin; Messikh Azeddine, Azeddine (Oxford Academic, 2018)
A Watson–Crick (WK) context-free grammar, a context-free grammar with productions whose right-hand sides contain nonterminals and double-stranded terminal strings, generates complete double-stranded strings under Watson–Crick complementarity. In this paper, we investigate the simpliﬁcation processes of Watson–Crick context-free grammars, which lead to deﬁning Chomsky like normal form for Watson–Crick context-free grammars. The main result of the paper is a modiﬁed CYK (Cocke–Younger–Kasami) algorithm for Watson–Crick context-free grammars in WK-Chomsky normal form, allowing to parse double-stranded strings in O(n^6) time.