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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Paun, G.: Computing with membranes. J. Comput. Syst. Sci. 61(1), 108–143 (2000)
Paun, G., Rozenberg, G.: A guide to membrane computing. Theor. Comput. Sci. 287(1), 73–100 (2002)
Paun, G.: Introduction to membrane computing. In: Ciobanu, G., Paun, G., Pérez-Jiménez, M.J. (eds.) Applications of Membrane Computing, pp. 1–42. Springer, Heidelberg (2006)
Zhang, X., Liu, Y., Luo, B., Pan, L.: Computational power of tissue P systems for generating control languages. Inf. Sci. 278, 285–297 (2014)
Zeng, X., Xu, L., Liu, X., Pan, L.: On languages generated by spiking neural P systems with weights. Inf. Sci. 278, 423–433 (2014)
Wang, X., Song, T., Gong, F., Zheng, P.: On the computational power of spiking neural P systems with self-organization. Sci. Rep. 6, 27624 (2016)
Freund, R.: An integrating view on DNA computing and membrane computing. In: Proceedings of the 9th WSEAS International Conference on Evolutionary Computing, Sofia, Bulgaria, pp. 15–20 (2008)
Freund, R., Paun, G., Rozernberg, G., Salomaa, A.: Watson-Crick finite automata. DIMACS Ser. Discret. Math. Theor. Comput. Sci. 48, 297–327 (1999)
Pǎun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer-Verlag, Heidelberg (1998)
Mohd Tamrin, M., Turaev, S., Tengku Sembok, T.M.: Weighted Watson-Crick automata. In: The 21st National Symposium on Mathematical Sciences (2013)
Czeizler, E., Czeizler, E.: A short survey on Watson-Crick automata. Bull. EATCS 88, 104–119 (2006)
Lpez, V.F., Ramiro Aguilar, L.A., Moreno, M.N., Corchado, J.M.: Grammatical inference with bioinformatics criteria. Neurocomputing 75(1), 88–97 (2012)
Sutapa, D., Mukhopadhyay, S.: A composite method based on formal grammar and DNA structural features in detecting human polymerase II promoter region. PLoS ONE 8(2), e54843 (2013)
Okawa, S., Hirose, S.: The relations among Watson-Crick automata and their relations with context-free languages. IEICE Trans. Inf. Syst. E 89(D(10)), 2591–2599 (2006)
Subramanian, K.G., Venkat, I., Mahalingam, K.: Context-free systems with a complementarity relation. In: Bio-Inspired Computing Theories and Applications (BIC-TA) (2011)
Subramanian, K., Hemalatha, S., Venkat, I.: On Watson-Crick automata. In: Proceedings of the Second International Conference on Computer Science, Engineering and Information Technology, CCSEIT 2012, Coimbatore, India, pp. 151–156 (2012)
Mohamad Zulkufli, N., Turaev, S., Mohd Tamrin, M., Messikh, A.: Watson-Crick linear grammars. In: The Second International Conference on Advanced Data and Information Engineering, DaEng 2015, Bali, Indonesia. Lecture Notes in Electrical Engineering (2015, to appear)
Mohamad Zulkufli, N., Turaev, S., Mohd Tamrin, M., Messikh, A.: Closure properties of Watson-Crick grammars. In: Proceedings of The 2nd Innovation and Analytics Conference and Exhibition (IACE), vol. 1691, p. 040032. AIP Publishing (2015)
Mohamad Zulkufli, N., Turaev, S., Mohd Tamrin, M., Messikh, A., Alshaikhli, I.F.T.: Computational properties of Watson-Crick context-free grammars. In: 2015 4th International Conference on Advanced Computer Science Applications and Technologies (ACSAT), pp. 186–191, December 2015
Mohamad Zulkufli, N.L., Turaev, S., Mohd Tamrin, M.I., Messikh, A.: Generative power and closure properties of Watson-Crick grammars. Appl. Comput. Intell. Soft Comput. 2016, 12 p. (2016)
Linz, P.: An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers Inc., Burlington (2006)
Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, vol. 1-3. Springer-Verlag, Heidelberg (1997)
Dassow, J.: Grammars with regulated rewriting. In: Martín-Vide, C., Mitrana, V., Paun, G. (eds.) Formal Languages and Applications, vol. 148, pp. 249–273. Springer, Heidelberg (2004)
Dassow, J., Paun, G.: Regulated Rewriting in Formal Language Theory. Springer Publishing Company, Heidelberg (2012)
Acknowledgements
This work has been supported through International Islamic University Endowment B research grant EDW B14-136-1021 and Fundamental Research Grant Scheme FRGS13-066-0307, Ministry of Education, Malaysia.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Mohamad Zulkufli, N.L., Turaev, S., Tamrin, M.I.M., Messikh, A. (2016). The Computational Power of Watson-Crick Grammars: Revisited. In: Gong, M., Pan, L., Song, T., Zhang, G. (eds) Bio-inspired Computing – Theories and Applications. BIC-TA 2016. Communications in Computer and Information Science, vol 681. Springer, Singapore. https://doi.org/10.1007/978-981-10-3611-8_20
Download citation
DOI: https://doi.org/10.1007/978-981-10-3611-8_20
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-3610-1
Online ISBN: 978-981-10-3611-8
eBook Packages: Computer ScienceComputer Science (R0)