×

Watson-Crick D0L systems: The power of one transition. (English) Zbl 1022.68069

Summary: We investigate the class of functions computable by uni-transitional Watson-Crick D0L systems: only one complementarity transition is possible during each derivation. The class is characterized in terms of a certain min-operation applied to \(\mathbb Z\)-rational functions. We also exhibit functions outside the class, and show that the basic decision problems are equivalent or harder than a celebrated open problem. For instance, the latter alternative applies to the growth-bound problem for functions in the class.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adleman, L., Molecular computation of solutions to combinatorial problems, Science, 266, 1021-1024 (1994)
[2] J. Csima, E. Csuhaj Varjú, A. Salomaaa, Power and size of extended Watson-Crick L systems, TUCS Report 424, Turku Centre for Computer Science, Turku, 2001, Theoret. Comput. Sci., in preparation.; J. Csima, E. Csuhaj Varjú, A. Salomaaa, Power and size of extended Watson-Crick L systems, TUCS Report 424, Turku Centre for Computer Science, Turku, 2001, Theoret. Comput. Sci., in preparation.
[3] Gruska, J., Foundations of Computing (1997), International Thomson Computer Press: International Thomson Computer Press London
[4] Honkala, J.; Salomaa, A., Watson-Crick D0L systems with regular triggers, Theoret. Comput. Sci., 259, 689-698 (2001) · Zbl 0972.68099
[5] Kuich, W.; Salomaa, A., Semirings, Automata, Languages (1986), Springer: Springer Berlin, Heidelberg, New York
[6] Mihalache, V.; Salomaa, A., Lindenmayer and DNAWatson-Crick D0L systems, EATCS Bull., 62, 160-175 (1997) · Zbl 0880.68075
[7] Mihalache, V.; Salomaa, A., Language-theoretic aspects of DNA complementarity, Theoret. Comput. Sci., 250, 163-178 (2001) · Zbl 0952.68060
[8] Păun, G.; Rozenberg, G.; Salomaa, A., DNA Computing. New Computing Paradigms (1998), Springer: Springer Berlin · Zbl 0940.68053
[9] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072
[10] Salomaa, A., Turing, Watson-Crick and Lindenmayer, Aspects of DNA complementarity, (Calude, C. S.; Casti, J.; Dinneen, M. J., Unconventional Models of Computation (1998), Springer: Springer Berlin), 94-107 · Zbl 0901.68055
[11] Salomaa, A., Watson-Crick walks and roads in D0L graphs, Acta Cybernet., 14, 179-192 (1999) · Zbl 0959.68061
[12] Salomaa, A., Uni-transitional Watson-Crick D0L systems, Theoret. Comput. Sci., 281, 537-553 (2002) · Zbl 0996.68085
[13] (Salomaa, A.; Rozenberg, G., Handbook of Formal Languages (1997), Springer: Springer Berlin) · Zbl 0866.68057
[14] Salomaa, A.; Soittola, M., Automata—Theoretic Aspects of Formal Power Series (1978), Springer: Springer New York · Zbl 0377.68039
[15] P. Sosı́k, D0L Systems + Watson-Crick Complement=Universal Computation, Lecture Notes in Computer Science, Vol. 2055, Springer, Berlin, pp. 308-320.; P. Sosı́k, D0L Systems + Watson-Crick Complement=Universal Computation, Lecture Notes in Computer Science, Vol. 2055, Springer, Berlin, pp. 308-320.
[16] P. Sosı́k, Watson-Crick D0L systems: generative power and undecidable problems, submitted for publication.; P. Sosı́k, Watson-Crick D0L systems: generative power and undecidable problems, submitted for publication.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.