Cover Image

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

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

Full description

Saved in:
Bibliographic Details
Main Authors: Mohamad Zulkufli, Nurul Liyana, Turaev, Sherzod, Mohd Tamrin, Mohd Izzuddin, Messikh Azeddine, Azeddine
Format: Article
Language:English
English
English
Published: Oxford Academic 2018
Subjects:
QA Mathematics
QA75 Electronic computers. Computer science
Online Access:http://irep.iium.edu.my/61503/1/Watson%E2%80%93Crick%20Context-Free%20Grammars-%20Grammar%20Simpli%EF%AC%81cations%20and%20a%20Parsing%20Algorithm.pdf
http://irep.iium.edu.my/61503/7/61503_Watson-crick%20context-free%20grammars%20Grammar%20simplifications%20and%20a%20parsing%20algorithm_scopus.pdf
http://irep.iium.edu.my/61503/12/61503_Watson-crick%20context-free%20grammars%20Grammar%20simplifications%20and%20a%20parsing%20algorithm_WOS.pdf
http://irep.iium.edu.my/61503/
https://academic.oup.com/comjnl/advance-article/doi/10.1093/comjnl/bxx128/4796924
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.iium.irep.61503
record_format dspace
spelling my.iium.irep.615032019-01-24T08:26:39Z http://irep.iium.edu.my/61503/ Watson–Crick context-free grammars: Grammar simplifications and a parsing algorithm Mohamad Zulkufli, Nurul Liyana Turaev, Sherzod Mohd Tamrin, Mohd Izzuddin Messikh Azeddine, Azeddine QA Mathematics QA75 Electronic computers. Computer science 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. Oxford Academic 2018-01-10 Article PeerReviewed application/pdf en http://irep.iium.edu.my/61503/1/Watson%E2%80%93Crick%20Context-Free%20Grammars-%20Grammar%20Simpli%EF%AC%81cations%20and%20a%20Parsing%20Algorithm.pdf application/pdf en http://irep.iium.edu.my/61503/7/61503_Watson-crick%20context-free%20grammars%20Grammar%20simplifications%20and%20a%20parsing%20algorithm_scopus.pdf application/pdf en http://irep.iium.edu.my/61503/12/61503_Watson-crick%20context-free%20grammars%20Grammar%20simplifications%20and%20a%20parsing%20algorithm_WOS.pdf 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 https://academic.oup.com/comjnl/advance-article/doi/10.1093/comjnl/bxx128/4796924 10.1093/comjnl/bxx128
institution Universiti Islam Antarabangsa Malaysia
building IIUM Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider International Islamic University Malaysia
content_source IIUM Repository (IREP)
url_provider http://irep.iium.edu.my/
language English
English
English
topic QA Mathematics
QA75 Electronic computers. Computer science
spellingShingle QA Mathematics
QA75 Electronic computers. Computer science
Mohamad Zulkufli, Nurul Liyana
Turaev, Sherzod
Mohd Tamrin, Mohd Izzuddin
Messikh Azeddine, Azeddine
Watson–Crick context-free grammars: Grammar simplifications and a parsing algorithm
description 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.
format Article
author Mohamad Zulkufli, Nurul Liyana
Turaev, Sherzod
Mohd Tamrin, Mohd Izzuddin
Messikh Azeddine, Azeddine
author_facet Mohamad Zulkufli, Nurul Liyana
Turaev, Sherzod
Mohd Tamrin, Mohd Izzuddin
Messikh Azeddine, Azeddine
author_sort Mohamad Zulkufli, Nurul Liyana
title Watson–Crick context-free grammars: Grammar simplifications and a parsing algorithm
title_short Watson–Crick context-free grammars: Grammar simplifications and a parsing algorithm
title_full Watson–Crick context-free grammars: Grammar simplifications and a parsing algorithm
title_fullStr Watson–Crick context-free grammars: Grammar simplifications and a parsing algorithm
title_full_unstemmed Watson–Crick context-free grammars: Grammar simplifications and a parsing algorithm
title_sort watson–crick context-free grammars: grammar simplifications and a parsing algorithm
publisher Oxford Academic
publishDate 2018
url http://irep.iium.edu.my/61503/1/Watson%E2%80%93Crick%20Context-Free%20Grammars-%20Grammar%20Simpli%EF%AC%81cations%20and%20a%20Parsing%20Algorithm.pdf
http://irep.iium.edu.my/61503/7/61503_Watson-crick%20context-free%20grammars%20Grammar%20simplifications%20and%20a%20parsing%20algorithm_scopus.pdf
http://irep.iium.edu.my/61503/12/61503_Watson-crick%20context-free%20grammars%20Grammar%20simplifications%20and%20a%20parsing%20algorithm_WOS.pdf
http://irep.iium.edu.my/61503/
https://academic.oup.com/comjnl/advance-article/doi/10.1093/comjnl/bxx128/4796924
_version_ 1643618783980421120
score 13.211869

Similar Items