Generative capacity of sticker systems with the presence of weights

Y. S. Gan, W. H. Fong, N. H. Sarmin, S. Turaev

Research output: Contribution to journalArticlepeer-review

Abstract

DNA computing involves computing models which use the recombination behaviour 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. A DNA-based computation model called a sticker system is an abstraction of the computations using the recombination behaviour as in Adleman’s experiment. In this paper, the generative capacity of several variants of bounded delay and unrestricted weighted sticker systems is investigated. The relation between families of languages generated by several variants of weighted sticker systems and weighted grammars is also presented.

Original languageEnglish
Pages (from-to)35-42
Number of pages8
JournalScienceAsia
Volume43
Issue number1
DOIs
Publication statusPublished - 2021
Externally publishedYes

Keywords

  • DNA computing
  • Formal language

ASJC Scopus subject areas

  • General

Fingerprint

Dive into the research topics of 'Generative capacity of sticker systems with the presence of weights'. Together they form a unique fingerprint.

Cite this