Time-Varying Distributed H Systems with Parallel Computations: the Problem is Solved
作者： Maurice Margenstern , Yurii Rogozhin , Sergey Verlan
DOI: 10.1007/978-3-540-24628-2_6
关键词:
摘要: In this article we show that time-varying distributed H systems (TVDH systems) with one component are able to model any type-0 grammar. Thus completely answered the question of constructing TVDH smallest degree which generate RE language using parallel nature molecular computations based on splicing operations. Another interesting point is proof a simulation system two and not grammars as it usually done in similar proofs.
springer.com
archives-ouvertes.fr
sci-hub.st 参考文章(11)
Andrei Paun, On Time-Varying H Systems. Bulletin of The European Association for Theoretical Computer Science. ,vol. 67, pp. 157- 164 ,(1999)
Gheorghe Paun, Arto Salomaa, Grzegorz Rozenberg, DNA Computing: New Computing Paradigms ,(1998)
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
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, Grzegorz Rozenberg, Arto Salomaa, Computing by splicing Theoretical Computer Science. ,vol. 168, pp. 321- 336 ,(1996) , 10.1016/S0304-3975(96)00082-5
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
Maurice Margenstern, Yurii Rogozhin, About Time-Varying Distributed H Systems international workshop on dna based computers. pp. 53- 62 ,(2000) , 10.1007/3-540-44992-2_5
Maurice Margenstern, Yurii Rogozhin, Time-Varying Distributed H-Systems of Degree 2 Generate All Recursively Enumerable Languages Where Mathematics, Computer Science, Linguistics and Biology Meet. pp. 399- 407 ,(2001) , 10.1007/978-94-015-9634-3_35
Sergey Verlan, A Frontier Result on Enhanced Time-Varying Distributed H Systems with Parallel Computations descriptional complexity of formal systems. pp. 221- 232 ,(2003)
Sheng Yu, Masami Ito, Gheorghe Paun, Words, Semigroups, and Transductions World Scientific Publishing Co., Inc.. ,(2001)