Watson–Crick context-free grammars: Grammar simplifications and a parsing algorithm

Mohamad Zulkufli, Nurul Liyana and Turaev, Sherzod and Mohd Tamrin, Mohd Izzuddin and Messikh Azeddine, Azeddine (2018) Watson–Crick context-free grammars: Grammar simplifications and a parsing algorithm. The Computer Journal :Section A: Computer Science Theory, Methods and Tools. pp. 1-13. ISSN 0010-4620 E-ISSN 1460-2067

Preview	PDF Download (783kB) | Preview
Preview	PDF Download (408kB) | Preview
Preview	PDF Download (312kB) | Preview

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.

Item Type:	Article (Journal)
Additional Information:	6846/61503
Uncontrolled Keywords:	NA Computing; formal languages; parsing algorithms; Watson–Crick grammars; Watson– Crick automata; grammar simplifications; context-free grammars
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Computer Science
Depositing User:	Dr. Sherzod Turaev
Date Deposited:	24 Jan 2018 09:18
Last Modified:	24 Jan 2019 16:26
URI:	http://irep.iium.edu.my/id/eprint/61503

Actions (login required)

View Item