Sticker systems. (English) Zbl 0908.68058

Summary: 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.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI


[1] Adleman, L.M., Molecular computation of solutions to combinatorial problems, Science, 226, 1021-1024, (1994)
[2] Csuhaj-Varju, E.; Freund, L.; Kari, L.; Păun, Gh., DNA computing based on splicing: universality results, () · Zbl 0914.68072
[3] Culik, K., A purely homomorphic characterization of recursively enumerable sets, J. ACM, 26, 345-350, (1979) · Zbl 0395.68076
[4] Engelfriet, J.; Rozenberg, G., Fixed point languages, equality languages, and representations of recursively enumerable languages, J. ACM, 27, 499-518, (1980) · Zbl 0475.68047
[5] Ginsburg, S., The mathematical theory of context-free languages, (1966), McGraw-Hill New York · Zbl 0184.28401
[6] Head, T.; Păun, Gh.; Pixton, D., Language theory and molecular genetics. generative mechanisms suggested by DNA recombination, ()
[7] L. Kari, Gh. Păun, G. Rozenberg, A. Salomaa, S. Yu, DNA computing, sticker systems, and universality, Acta Inform. to appear.
[8] Păun, Gh., Regular extended H systems are computationally universal, J. automat. lang. combin., 1, 1, 27-36, (1996) · Zbl 0867.68043
[9] Păun, Gh.; Rozenberg, G.; Salomaa, A., Computing by splicing, Theoret. comput. sci., 168, 2, 321-336, (1996) · Zbl 0874.68117
[10] Păun, Gh.; Rozenberg, G.; Salomaa, A., Molecular computing. new computability paradigms, (1998), Springer Heidelberg
[11] Păun, Gh.; Salomaa, A., DNA computing based on the splicing operation, Math. japonica, 43, 3, 607-632, (1996) · Zbl 0852.68028
[12] ()
[13] Salomaa, A., Equality sets for homomorphisms of free monoids, Acta cybernet., 4, 127-139, (1978) · Zbl 0407.68077
[14] Salomaa, A., Jewels of formal language theory, (1981), Computer Science Press Rockville, MD · Zbl 0487.68063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.