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

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

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/
http://irep.iium.edu.my/61503/
http://irep.iium.edu.my/61503/
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
id iium-61503
recordtype eprints
spelling iium-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 E-ISSN 1460-2067 https://academic.oup.com/comjnl/advance-article/doi/10.1093/comjnl/bxx128/4796924 10.1093/comjnl/bxx128
repository_type Digital Repository
institution_category Local University
institution International Islamic University Malaysia
building IIUM Repository
collection Online Access
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/
http://irep.iium.edu.my/61503/
http://irep.iium.edu.my/61503/
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
first_indexed 2023-09-18T21:27:14Z
last_indexed 2023-09-18T21:27:14Z
_version_ 1777412273192566784

Similar Items