Watson–Crick Context-Free Grammars: Grammar Simplifications and a Parsing Algorithm. (10th January 2018)

• Record Type: Journal Article
• Authors: Mohamad Zulkufli, Nurul Liyana; Turaev, Sherzod; Mohd Tamrin, Mohd Izzuddin; Messikh, Azeddine
• Editors: Clifford, Raphael
• Is Part Of: Computer journal. Volume 61:Number 9(2018)
• Page Start: 1361
• Page End: 1373
• Publication Date: 2018-01-10
• Subjects: DNA Computing -- formal languages -- parsing algorithms -- Watson–Crick grammars -- Watson–Crick automata -- grammar simplifications -- context-free grammars; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx128
• Languages: English
• ISSNs: 0010-4620

Abstract

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.