A boundary result on enhanced time-varying distributed H systems with parallel computations
作者： Sergey Verlan
DOI: 10.1016/J.TCS.2005.03.056
关键词:
摘要: Enhanced time-varying distributed H systems (ETVDH systems) are a variant of (TVDH systems), which is well-known theoretical model DNA computing based on splicing. We show that ETVDH with 2 components, i.e., having two sets rules act periodically, may generate all recursively enumerable languages by simulating type-0 grammars. also present new approach to control the computations can be used in other models
core.ac.uk
archives-ouvertes.fr
elsevier.com
sci-hub.se 参考文章(16)
Gheorghe Paun, Arto Salomaa, Grzegorz Rozenberg, DNA Computing: New Computing Paradigms (Texts in Theoretical Computer Science. An EATCS Series) Springer-Verlag New York, Inc.. ,(2006)
Maurice Margenstern, Yurii Rogozhin, Sergey Verlan, Time-Varying Distributed H Systems with Parallel Computations: the Problem is Solved international workshop on dna based computers. ,vol. 2943, pp. 48- 54 ,(2003) , 10.1007/978-3-540-24628-2_6
Gheorghe Paun, Arto Salomaa, Grzegorz Rozenberg, DNA Computing: New Computing Paradigms ,(1998)
Thomas Head, Gheorghe Păun, Dennis Pixton, Language theory and molecular genetics: generative mechanisms suggested by DNA recombination Handbook of formal languages, vol. 2. pp. 295- 360 ,(1997) , 10.1007/978-3-662-07675-0_7
Handbook of Formal Languages Springer-Verlag. ,(1997) , 10.1007/978-3-642-59126-6
Maurice Margenstern, Yurii Rogozhin, Sergey Verlan, Time-Varying Distributed H Systems of Degree 2 Can Carry Out Parallel Computations international workshop on dna based computers. ,vol. 2568, pp. 326- 336 ,(2002) , 10.1007/3-540-36440-4_29
Rajeev Motwani, John E. Hopcroft, Jeffrey D. Ullman, Rotwani, Introduction to Automata Theory, Languages, and Computation ,(1979)
Tom Head, Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors. Bulletin of Mathematical Biology. ,vol. 49, pp. 737- 759 ,(1987) , 10.1007/BF02481771
Gheorghe Păun, Regular extended H systems are computationally universal Journal of Automata, Languages and Combinatorics. ,vol. 1, pp. 27- 36 ,(1996)
Gheorghe Păun, DNA computing based on splicing: universality results Theoretical Computer Science. ,vol. 231, pp. 275- 296 ,(2000) , 10.1016/S0304-3975(99)00104-8