Probabilistic Semi–Simple Splicing System and Its Characteristics

Authors

  • Mathuri Selvarajoo Department of Mathematical Sciences, Faculty of Science, Universiti Teknologi Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia
  • Fong Wan Heng Ibnu Sina Institute for Fundamental Science Studies, Universiti Teknologi Malaysia, 81310 UTM Johor Bharu, Johor, Malaysia
  • Nor Haniza Sarmin Department of Mathematical Sciences, Faculty of Science, Universiti Teknologi Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia
  • Sherzod Turaev Department of Computer Science, Kulliyyah of Information and Communication Technology, International Islamic University Malaysia, 53100 Kuala Lumpur, Malaysia

DOI:

https://doi.org/10.11113/jt.v62.1884

Keywords:

DNA computing, probabilistic splicing systems, splicing languages, regular languages

Abstract

The concept of splicing system was first introduced by Head in 1987. This model has been introduced to investigate the recombinant behavior of DNA molecules. Splicing systems with finite sets of axioms only generate regular languages. Hence, different restrictions have been considered to increase the computational power up to the recursively enumerable languages. Recently, probabilistic splicing systems have been introduced where probabilities are initially associated with the axioms, and the probability of a generated string is computed by multiplying the probabilities of all occurrences of the initial strings in the computation of the string. In this paper, some properties of probabilistic semi-simple splicing systems, which are special types of probabilistic splicing systems, are investigated. We prove that probabilistic semi-simple splicing systems can also increase the generative power of the generated languages.

References

L. Adleman. 1994. Science. 266: 1021–1024.

T. Head. 1987. Bull. Math.Biology. 49: 737–759

D. Pixton. 1996. Discrete Applied Mathematics. 69: 101–124.

Sherzod Turaev, Mathuri Selvarajoo, Fong Wan Heng, Nor Haniza Sarmin. 2013. Advanced Methods for Computational Collective Intelligence. New York: Springer. 457: 259–268.

G. Paun, G. Rozenberg, A. Salomaa. 1998. Handbook of Formal Languages: Vol.1. Word, language, grammar. Springer-Verlag.

E. Goode, D. Pixton. 1996. Discrete Applied Math. 72: 96–107.

T. Fowler. 2011. The Generative Power of Probabilistic and Weighted Context-Free Grammars. Springer-Verlag. 68: 57–71.

Downloads

Published

2013-05-15

Issue

Vol. 62 No. 3: Special Edition

Section

Science and Engineering

License

Copyright of articles that appear in Jurnal Teknologi belongs exclusively to Penerbit Universiti Teknologi Malaysia (Penerbit UTM Press). This copyright covers the rights to reproduce the article, including reprints, electronic reproductions, or any other reproductions of similar nature.

How to Cite

Probabilistic Semi–Simple Splicing System and Its Characteristics. (2013). Jurnal Teknologi, 62(3). https://doi.org/10.11113/jt.v62.1884