In this paper, we propose an architecture of oritatami systems, a mathematical model of RNA cotranscriptional folding, with which one can simulate an arbitrary nondeterministic finite automaton (NFA) in a unified manner. The oritatami system is known to be Turing-universal but the simulation available so far requires 542 bead types and O(t4log2t) steps in order to simulate t steps of a Turing machine. The architecture we propose employs only 337 bead types and requires just O(t|Q|4|Σ|2) steps to simulate an NFA with a state set Q working on a word of length t over an alphabet Σ.
|Number of pages||24|
|Journal||Theoretical Computer Science|
|Publication status||Published - 2021 May 16|
Bibliographical noteFunding Information:
This work has been supported primarily by the Basic Science Research Program ( NRF-2018R1D1A1A09084107 ) to Han, the NRF grant funded by the Korea government (MSIT) (No. 2020R1F1A1072738 ) to Kim, JSPS KAKENHI Grant-in-Aids for Young Scientists (A) No. 16H05854 , for Challenging Research (Exploratory) No. 18K19779 , and for Scientific Research (C) No. 20K11672 to Seki, JSPS-NRF Bilateral Program No. YB29004 to Han and Seki, and JST Program to Disseminate Tenure Tracking System, MEXT, Japan No. 6F36 to Seki. Kim has been also supported by NIH R01GM109459 , NSF 's CCF01526485 , DMS-1800443 , the Southeast Center for Mathematics and Biology, an NSF-Simons Research Center for Mathematics and Complex Biological Systems, under NSF 's DMS-1764406 and the Simons Foundation Grant 594594 .
© 2020 Elsevier B.V.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)