Bidirectional sticker systems.
We introduce two-sided sticker systems, the two-sided variant of a computability model introduced as an abstraction of Adleman's style of DNA computing and of the matching of the so-called Watson-Crick complements. Several types of sticker systems are shown to have the same power as regular grammars, one variant is found to represent the linear languages, and another one is proved to be able to represent any recursively enumerable language. From this result we infer that any recursively enumerable language can be represented as the projection of the intersection of two minimal linear languages.
Freund
R
R
Department of Computer Science, Vienna University of Technology, Wien, Austria. rudi@logic.at
Păun
G
G
Rozenberg
G
G
Salomaa
A
A
D001482:Base Composition; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D003205:Computing Methodologies; D004247:DNA / Q000737:chemistry* / Q000235:genetics*; D008957:Models, Genetic; D009690:Nucleic Acid Conformation; D011381:Programming Languages; D012984:Software
D004247:DNA