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

Nurul Liyana Mohamad Zulkufli; Sherzod Turaev; Mohd Izzuddin Mohd Tamrin; Azeddine Messikh

doi:10.1093/comjnl/bxx128

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

Nurul Liyana Mohamad Zulkufli
, Sherzod Turaev
, Mohd Izzuddin Mohd Tamrin
, Azeddine Messikh

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

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 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(n⁶) time.

Original language	English
Pages (from-to)	1361-1373
Number of pages	13
Journal	Computer Journal
Volume	61
Issue number	9
DOIs	https://doi.org/10.1093/comjnl/bxx128
Publication status	Published - Sept 1 2018
Externally published	Yes

Keywords

Context-free grammars
DNA computing
Formal languages
Grammar simplifications
Parsing algorithms
Watson-Crick automata
Watson-Crick grammars

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1093/comjnl/bxx128

Cite this

@article{94685f8d20254fdf83a86b48340da40c,

title = "Watson-crick context-free grammars: Grammar simplifications and a parsing algorithm",

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 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.",

keywords = "Context-free grammars, DNA computing, Formal languages, Grammar simplifications, Parsing algorithms, Watson-Crick automata, Watson-Crick grammars",

author = "Zulkufli, \{Nurul Liyana Mohamad\} and Sherzod Turaev and Tamrin, \{Mohd Izzuddin Mohd\} and Azeddine Messikh",

year = "2018",

month = sep,

day = "1",

doi = "10.1093/comjnl/bxx128",

language = "English",

volume = "61",

pages = "1361--1373",

journal = "Computer Journal",

issn = "0010-4620",

publisher = "Oxford University Press",

number = "9",

}

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

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 - https://www.scopus.com/pages/publications/85055204433

UR - https://www.scopus.com/pages/publications/85055204433#tab=citedBy

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 -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this