The computational power of Watson-Crick grammars: Revisited

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

doi:10.1007/978-981-10-3611-8_20

The computational power of Watson-Crick grammars: Revisited

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

Abstract

A Watson-Crick finite automaton is one of DNA computational models using the Watson-Crick complementarity feature of deoxyribonucleic acid (DNA). We are interested in investigating a grammar counterpart of Watson-Crick automata. In this paper, we present results concerning the generative power of Watson-Crick (regular, linear, context-free) grammars. We show that the family of Watson-Crick context-free languages is included in the family of matrix languages.

Original language	English
Title of host publication	Bio-inspired Computing – Theories and Applications - 11th International Conference, BIC-TA 2016, Revised Selected Papers
Editors	Linqiang Pan, Maoguo Gong, Tao Song, Tao Song, Gexiang Zhang
Publisher	Springer Verlag
Pages	215-225
Number of pages	11
ISBN (Print)	9789811036101
DOIs	https://doi.org/10.1007/978-981-10-3611-8_20
Publication status	Published - 2016
Externally published	Yes
Event	11th International Conference on Bio-inspired Computing – Theories and Applications, BIC-TA 2016 - Xian, China Duration: Oct 28 2016 → Oct 30 2016

Publication series

Name	Communications in Computer and Information Science
Volume	681
ISSN (Print)	1865-0929

Conference

Conference	11th International Conference on Bio-inspired Computing – Theories and Applications, BIC-TA 2016
Country/Territory	China
City	Xian
Period	10/28/16 → 10/30/16

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1007/978-981-10-3611-8_20

Cite this

Mohamad Zulkufli, N. L., Turaev, S., Mohd Tamrin, M. I., & Messikh, A. (2016). The computational power of Watson-Crick grammars: Revisited. In L. Pan, M. Gong, T. Song, T. Song, & G. Zhang (Eds.), Bio-inspired Computing – Theories and Applications - 11th International Conference, BIC-TA 2016, Revised Selected Papers (pp. 215-225). (Communications in Computer and Information Science; Vol. 681). Springer Verlag. https://doi.org/10.1007/978-981-10-3611-8_20

The computational power of Watson-Crick grammars: Revisited. / Mohamad Zulkufli, Nurul Liyana; Turaev, Sherzod; Mohd Tamrin, Mohd Izzuddin et al.
Bio-inspired Computing – Theories and Applications - 11th International Conference, BIC-TA 2016, Revised Selected Papers. ed. / Linqiang Pan; Maoguo Gong; Tao Song; Tao Song; Gexiang Zhang. Springer Verlag, 2016. p. 215-225 (Communications in Computer and Information Science; Vol. 681).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Mohamad Zulkufli, NL, Turaev, S, Mohd Tamrin, MI & Messikh, A 2016, The computational power of Watson-Crick grammars: Revisited. in L Pan, M Gong, T Song, T Song & G Zhang (eds), Bio-inspired Computing – Theories and Applications - 11th International Conference, BIC-TA 2016, Revised Selected Papers. Communications in Computer and Information Science, vol. 681, Springer Verlag, pp. 215-225, 11th International Conference on Bio-inspired Computing – Theories and Applications, BIC-TA 2016, Xian, China, 10/28/16. https://doi.org/10.1007/978-981-10-3611-8_20

Mohamad Zulkufli NL, Turaev S, Mohd Tamrin MI, Messikh A. The computational power of Watson-Crick grammars: Revisited. In Pan L, Gong M, Song T, Song T, Zhang G, editors, Bio-inspired Computing – Theories and Applications - 11th International Conference, BIC-TA 2016, Revised Selected Papers. Springer Verlag. 2016. p. 215-225. (Communications in Computer and Information Science). doi: 10.1007/978-981-10-3611-8_20

Mohamad Zulkufli, Nurul Liyana ; Turaev, Sherzod ; Mohd Tamrin, Mohd Izzuddin et al. / The computational power of Watson-Crick grammars : Revisited. Bio-inspired Computing – Theories and Applications - 11th International Conference, BIC-TA 2016, Revised Selected Papers. editor / Linqiang Pan ; Maoguo Gong ; Tao Song ; Tao Song ; Gexiang Zhang. Springer Verlag, 2016. pp. 215-225 (Communications in Computer and Information Science).

@inproceedings{6bf728594b3341f2adc1629a4c20c02e,

title = "The computational power of Watson-Crick grammars: Revisited",

abstract = "A Watson-Crick finite automaton is one of DNA computational models using the Watson-Crick complementarity feature of deoxyribonucleic acid (DNA). We are interested in investigating a grammar counterpart of Watson-Crick automata. In this paper, we present results concerning the generative power of Watson-Crick (regular, linear, context-free) grammars. We show that the family of Watson-Crick context-free languages is included in the family of matrix languages.",

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

note = "Publisher Copyright: {\textcopyright} Springer Nature Singapore Pte Ltd. 2016.; 11th International Conference on Bio-inspired Computing – Theories and Applications, BIC-TA 2016 ; Conference date: 28-10-2016 Through 30-10-2016",

year = "2016",

doi = "10.1007/978-981-10-3611-8_20",

language = "English",

isbn = "9789811036101",

series = "Communications in Computer and Information Science",

publisher = "Springer Verlag",

pages = "215--225",

editor = "Linqiang Pan and Maoguo Gong and Tao Song and Tao Song and Gexiang Zhang",

booktitle = "Bio-inspired Computing – Theories and Applications - 11th International Conference, BIC-TA 2016, Revised Selected Papers",

}

TY - GEN

T1 - The computational power of Watson-Crick grammars

T2 - 11th International Conference on Bio-inspired Computing – Theories and Applications, BIC-TA 2016

AU - Mohamad Zulkufli, Nurul Liyana

AU - Turaev, Sherzod

AU - Mohd Tamrin, Mohd Izzuddin

AU - Messikh, Azeddine

N1 - Publisher Copyright: © Springer Nature Singapore Pte Ltd. 2016.

PY - 2016

Y1 - 2016

N2 - A Watson-Crick finite automaton is one of DNA computational models using the Watson-Crick complementarity feature of deoxyribonucleic acid (DNA). We are interested in investigating a grammar counterpart of Watson-Crick automata. In this paper, we present results concerning the generative power of Watson-Crick (regular, linear, context-free) grammars. We show that the family of Watson-Crick context-free languages is included in the family of matrix languages.

AB - A Watson-Crick finite automaton is one of DNA computational models using the Watson-Crick complementarity feature of deoxyribonucleic acid (DNA). We are interested in investigating a grammar counterpart of Watson-Crick automata. In this paper, we present results concerning the generative power of Watson-Crick (regular, linear, context-free) grammars. We show that the family of Watson-Crick context-free languages is included in the family of matrix languages.

UR - http://www.scopus.com/inward/record.url?scp=85010070482&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010070482&partnerID=8YFLogxK

U2 - 10.1007/978-981-10-3611-8_20

DO - 10.1007/978-981-10-3611-8_20

M3 - Conference contribution

AN - SCOPUS:85010070482

SN - 9789811036101

T3 - Communications in Computer and Information Science

SP - 215

EP - 225

BT - Bio-inspired Computing – Theories and Applications - 11th International Conference, BIC-TA 2016, Revised Selected Papers

A2 - Pan, Linqiang

A2 - Gong, Maoguo

A2 - Song, Tao

A2 - Zhang, Gexiang

PB - Springer Verlag

Y2 - 28 October 2016 through 30 October 2016

ER -

The computational power of Watson-Crick grammars: Revisited

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this