Bibliographic Details
| Title: |
A general architecture of oritatami systems for simulating arbitrary finite automata. |
| Authors: |
Han, Yo-Sub1 (AUTHOR), Kim, Hwee2 (AUTHOR), Masuda, Yusei3 (AUTHOR), Seki, Shinnosuke1,3 (AUTHOR) s.seki@uec.ac.jp |
| Source: |
Theoretical Computer Science. May2021, Vol. 870, p29-52. 24p. |
| Subjects: |
Finite state machines, Turing machines, Molecular self-assembly, Mathematical models, Robots |
| Abstract: |
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 (t 4 log 2 t) 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 Σ. [ABSTRACT FROM AUTHOR] |
|
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
