Generative Power and Closure Properties of Watson-Crick Grammars
We define WK linear grammars, as an extension of WK regular grammars with linear grammar rules, and WK context-free grammars, thus investigating their computational power and closure properties. We show that WK linear grammars can generate some context-sensitive languages. Moreover, we demonstrate t...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2016-01-01
|
| Series: | Applied Computational Intelligence and Soft Computing |
| Online Access: | http://dx.doi.org/10.1155/2016/9481971 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849685772316180480 |
|---|---|
| author | Nurul Liyana Mohamad Zulkufli Sherzod Turaev Mohd Izzuddin Mohd Tamrin Azeddine Messikh |
| author_facet | Nurul Liyana Mohamad Zulkufli Sherzod Turaev Mohd Izzuddin Mohd Tamrin Azeddine Messikh |
| author_sort | Nurul Liyana Mohamad Zulkufli |
| collection | DOAJ |
| description | We define WK linear grammars, as an extension of WK regular grammars with linear grammar rules, and WK context-free grammars, thus investigating their computational power and closure properties. We show that WK linear grammars can generate some context-sensitive languages. Moreover, we demonstrate that the family of WK regular languages is the proper subset of the family of WK linear languages, but it is not comparable with the family of linear languages. We also establish that the Watson-Crick regular grammars are closed under almost all of the main closure operations. |
| format | Article |
| id | doaj-art-c6f4b269cd5c44a5b9bfdef3c2fae013 |
| institution | DOAJ |
| issn | 1687-9724 1687-9732 |
| language | English |
| publishDate | 2016-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Applied Computational Intelligence and Soft Computing |
| spelling | doaj-art-c6f4b269cd5c44a5b9bfdef3c2fae0132025-08-20T03:22:58ZengWileyApplied Computational Intelligence and Soft Computing1687-97241687-97322016-01-01201610.1155/2016/94819719481971Generative Power and Closure Properties of Watson-Crick GrammarsNurul Liyana Mohamad Zulkufli0Sherzod Turaev1Mohd Izzuddin Mohd Tamrin2Azeddine Messikh3Kulliyyah of Information and Communication Technology, International Islamic University Malaysia, 53100 Kuala Lumpur, MalaysiaKulliyyah of Information and Communication Technology, International Islamic University Malaysia, 53100 Kuala Lumpur, MalaysiaKulliyyah of Information and Communication Technology, International Islamic University Malaysia, 53100 Kuala Lumpur, MalaysiaKulliyyah of Information and Communication Technology, International Islamic University Malaysia, 53100 Kuala Lumpur, MalaysiaWe define WK linear grammars, as an extension of WK regular grammars with linear grammar rules, and WK context-free grammars, thus investigating their computational power and closure properties. We show that WK linear grammars can generate some context-sensitive languages. Moreover, we demonstrate that the family of WK regular languages is the proper subset of the family of WK linear languages, but it is not comparable with the family of linear languages. We also establish that the Watson-Crick regular grammars are closed under almost all of the main closure operations.http://dx.doi.org/10.1155/2016/9481971 |
| spellingShingle | Nurul Liyana Mohamad Zulkufli Sherzod Turaev Mohd Izzuddin Mohd Tamrin Azeddine Messikh Generative Power and Closure Properties of Watson-Crick Grammars Applied Computational Intelligence and Soft Computing |
| title | Generative Power and Closure Properties of Watson-Crick Grammars |
| title_full | Generative Power and Closure Properties of Watson-Crick Grammars |
| title_fullStr | Generative Power and Closure Properties of Watson-Crick Grammars |
| title_full_unstemmed | Generative Power and Closure Properties of Watson-Crick Grammars |
| title_short | Generative Power and Closure Properties of Watson-Crick Grammars |
| title_sort | generative power and closure properties of watson crick grammars |
| url | http://dx.doi.org/10.1155/2016/9481971 |
| work_keys_str_mv | AT nurulliyanamohamadzulkufli generativepowerandclosurepropertiesofwatsoncrickgrammars AT sherzodturaev generativepowerandclosurepropertiesofwatsoncrickgrammars AT mohdizzuddinmohdtamrin generativepowerandclosurepropertiesofwatsoncrickgrammars AT azeddinemessikh generativepowerandclosurepropertiesofwatsoncrickgrammars |