TY - JOUR
T1 - Watson-crick context-free grammars
T2 - Grammar simplifications and a parsing algorithm
AU - Zulkufli, Nurul Liyana Mohamad
AU - Turaev, Sherzod
AU - Tamrin, Mohd Izzuddin Mohd
AU - Messikh, Azeddine
N1 - Funding Information:
This research was supported by Ministry of Education Malaysia and International Islamic University Malaysia through Fundamental Research Grant Scheme [FRGS13-066-0307].
Publisher Copyright:
© The British Computer Society 2018. All rights reserved.
PY - 2018/9/1
Y1 - 2018/9/1
N2 - 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 Chomskylike 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(n6) time.
AB - 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 Chomskylike 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(n6) time.
KW - Context-free grammars
KW - DNA computing
KW - Formal languages
KW - Grammar simplifications
KW - Parsing algorithms
KW - Watson-Crick automata
KW - Watson-Crick grammars
UR - http://www.scopus.com/inward/record.url?scp=85055204433&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85055204433&partnerID=8YFLogxK
U2 - 10.1093/comjnl/bxx128
DO - 10.1093/comjnl/bxx128
M3 - Article
AN - SCOPUS:85055204433
SN - 0010-4620
VL - 61
SP - 1361
EP - 1373
JO - Computer Journal
JF - Computer Journal
IS - 9
ER -