Watson–Crick Context-Free Grammars: Grammar Simplifications and a Parsing Algorithm. (10th January 2018) - Mohamad Zulkufli, Nurul Liyana
Abstract: 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 simplification processes of Watson–Crick context-free grammars, which lead to defining Chomsky-like normal form for Watson–Crick context-free grammars. The main result of the paper is a modified 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.