Generative capacity of sticker systems with the presence of weights

• Main Authors: Gan, Yee Siang, Fong, Wan Heng, Sarmin, Nor Haniza, Turaev, Sherzod
• Format: Article
• Language: English; English
• Published: Science Society of Thailand under Royal Patronage 2017
• Subjects: QA Mathematics; QA75 Electronic computers. Computer science
• Online Access: http://irep.iium.edu.my/53808/1/53808_Generative%20capacity%20of%20sticker%20systems.pdf; http://irep.iium.edu.my/53808/7/53808_Generative%20capacity%20of%20sticker%20systems_Scopus.pdf; http://irep.iium.edu.my/53808/; http://www.scienceasia.org/content/viewabstract.php?ms=8950&v=55&abst=1

DNA computing involves computing models which use the recombination behavior of DNA molecules as computation devices. This idea was successfully applied by Adleman in his biological experiment in order to show the solvability of the Hamiltonian path problem for larger instances. In 1998, a DNA based computation model, called sticker system, which is an abstraction of the computations using the recombination behavior as in Adleman’s experiment was proposed. In 2013, a new variant of sticker system using weights was introduced, namely the weighted sticker system. In this paper, the generative capacity for several variants of bounded delay and nonrestrictive weighted sticker systems are investigated. The relation between families of languages generated by several variants of weighted sticker systems and weighted grammars are also presented.