A general architecture of oritatami systems for simulating arbitrary finite automata

Yo Sub Han; Hwee Kim; Yusei Masuda; Shinnosuke Seki

doi:10.1016/j.tcs.2020.12.014

A general architecture of oritatami systems for simulating arbitrary finite automata

Yo Sub Han, Hwee Kim, Yusei Masuda, Shinnosuke Seki

College of Computing

Research output: Contribution to journal › Article › peer-review

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⁴log²⁡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|⁴|Σ|²) steps to simulate an NFA with a state set Q working on a word of length t over an alphabet Σ.

Original language	English
Pages (from-to)	29-52
Number of pages	24
Journal	Theoretical Computer Science
Volume	870
DOIs	https://doi.org/10.1016/j.tcs.2020.12.014
Publication status	Published - 2021 May 16

Bibliographical note

Funding 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 .

Publisher Copyright:
© 2020 Elsevier B.V.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/j.tcs.2020.12.014

Cite this

@article{b3f343a7d6f54e9991eec7e540dd7fea,

title = "A general architecture of oritatami systems for simulating arbitrary finite automata",

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(t4log2⁡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 Σ.",

author = "Han, {Yo Sub} and Hwee Kim and Yusei Masuda and Shinnosuke Seki",

note = "Funding 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 . Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2021",

month = may,

day = "16",

doi = "10.1016/j.tcs.2020.12.014",

language = "English",

volume = "870",

pages = "29--52",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - A general architecture of oritatami systems for simulating arbitrary finite automata

AU - Han, Yo Sub

AU - Kim, Hwee

AU - Masuda, Yusei

AU - Seki, Shinnosuke

N1 - Funding 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 . Publisher Copyright: © 2020 Elsevier B.V.

PY - 2021/5/16

Y1 - 2021/5/16

N2 - 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(t4log2⁡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 Σ.

AB - 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(t4log2⁡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 Σ.

UR - http://www.scopus.com/inward/record.url?scp=85098759155&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85098759155&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2020.12.014

DO - 10.1016/j.tcs.2020.12.014

M3 - Article

AN - SCOPUS:85098759155

SN - 0304-3975

VL - 870

SP - 29

EP - 52

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

A general architecture of oritatami systems for simulating arbitrary finite automata

Abstract

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this