Power and size of extended Watson-Crick \(L\) systems. (English) Zbl 1038.68075
Summary: A Watson-Crick \(D0L\) system is a language-theoretic model which is based on a \(D0L\) system and a letter-to-letter morphism, representing the Watson-Crick complementarity phenomenon of DNA. The two components are connected by a triggering mechanism. The computational capacity of these constructs is of particular interest. In this paper we prove that if the underlying systems are \(EDT0L\) systems or \(E0L\) systems, then these constructs are able to generate any recursively enumerable language. Moreover, to reach this power, Watson-Crick \(EDT0L\) systems with either two tables or a bounded number of non-terminals suffice.
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
Watson-Crick complementarity; Recursively enumerable language; Lindenmayer systems; \(D0L\) systems; Iterated morphismReferences:
| [1] | E. Csuhaj-Varjú, A. Salomaa, Networks of Watson-Crick \(DL\); E. Csuhaj-Varjú, A. Salomaa, Networks of Watson-Crick \(DL\) · Zbl 1200.68132 |
| [2] | V. Geffert, Context-free-like forms for phrase-structure grammars, MFCS’88, Lecture Notes in Computer Science, Vol. 324, Springer, Berlin, 1988, pp. 309-317.; V. Geffert, Context-free-like forms for phrase-structure grammars, MFCS’88, Lecture Notes in Computer Science, Vol. 324, Springer, Berlin, 1988, pp. 309-317. · Zbl 0652.68095 |
| [3] | Honkala, J.; Salomaa, A., Watson-Crick \(D0L\) systems with regular triggers, Theoret. Comput. Sci., 259, 689-698 (2001) · Zbl 0972.68099 |
| [4] | Mihalache, V.; Salomaa, A., Watson-Crick \(D0L\) systems, EATCS Bull., 62, 160-175 (1997) · Zbl 0880.68075 |
| [5] | Mihalache, V.; Salomaa, A., Language-theoretic aspects of DNA complementarity, Theoret. Comput. Sci., 250, 1-2, 163-178 (2001) · Zbl 0952.68060 |
| [6] | Rozenberg, G.; Salomaa, A., The Mathematical Theory of \(L\) Systems (1980), Academic Press: Academic Press New York, London · Zbl 0365.68072 |
| [7] | G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vols. I-III, Springer, Berlin, Heidelberg, New York, 1997.; G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vols. I-III, Springer, Berlin, Heidelberg, New York, 1997. · Zbl 0866.68057 |
| [8] | Salomaa, A., Turing, Watson-Crick and Lindenmayer. Aspects of DNA complementarity, (Calude, C. S.; Casti, J.; Dinneen, . J., Unconventional Models of Computation (1998), Springer: Springer Singapore, Berlin, Heidelberg, New York), 94-107 · Zbl 0901.68055 |
| [9] | Salomaa, A., Watson-Crick walks and roads on \(D0L\) Graphs, Acta Cybernet., 14, 1, 179-192 (1999) · Zbl 0959.68061 |
| [10] | Salomaa, A., Uni-transitional Watson-Crick \(D0L\) systems, Theoret. Comput. Sci., 281, 537-553 (2002) · Zbl 0996.68085 |
| [11] | A. Salomaa, Iterated morphism with complementarity on the DNA alphabet, TUCS Report 390, Turku Centre for Computer Science, Turku, February, 2001, Lecture Notes in Computer Science, Springer, to appear.; A. Salomaa, Iterated morphism with complementarity on the DNA alphabet, TUCS Report 390, Turku Centre for Computer Science, Turku, February, 2001, Lecture Notes in Computer Science, Springer, to appear. |
| [12] | Sosik, P., \(D0L System+ Watson\)-Crick Complementarity=Universal Computation, (Margenstern, M.; Rogozhin, Y., Machines, Computations and Universality, Proc. 3rd Internat. Conf. MCU 2001, Chisinau, Moldova, Lecture Notes in Computer Science, Vol. 2055 (2001), Springer: Springer Berlin, Heidelberg, New York), 308-319 · Zbl 0984.68088 |
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.
