Sticker systems

Sticker systems is a computational model which is an abstraction of the way that the Watson-Crick complementarity is used in DNA computing. We consider such systems of a general form, with blocks of arbitrary shapes to be annealed to the currently built sequences. We investigate the generative power of several variants of sticker systems. Characterizations of regular, linear, and recursively enumerable languages are obtained in this framework.

Authors

• Gheorghe Păun
• Grzegorz Rozenberg

Keywords

• DNA Computing
• Chomsky hierarchy
• Equality sets of morphisms
• Characterizations of recursively enumerable languages