A general architecture of oritatami systems for simulating arbitrary finite automata.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 150291708 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A general architecture of oritatami systems for simulating arbitrary finite automata. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Han%2C+Yo-Sub%22">Han, Yo-Sub</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Kim%2C+Hwee%22">Kim, Hwee</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Masuda%2C+Yusei%22">Masuda, Yusei</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Seki%2C+Shinnosuke%22">Seki, Shinnosuke</searchLink><relatesTo>1,3</relatesTo> (AUTHOR)<i> s.seki@uec.ac.jp</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. May2021, Vol. 870, p29-52. 24p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Finite+state+machines%22">Finite state machines</searchLink><br /><searchLink fieldCode="DE" term="%22Turing+machines%22">Turing machines</searchLink><br /><searchLink fieldCode="DE" term="%22Molecular+self-assembly%22">Molecular self-assembly</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+models%22">Mathematical models</searchLink><br /><searchLink fieldCode="DE" term="%22Robots%22">Robots</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=150291708 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.tcs.2020.12.014 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 24 StartPage: 29 Subjects: – SubjectFull: Finite state machines Type: general – SubjectFull: Turing machines Type: general – SubjectFull: Molecular self-assembly Type: general – SubjectFull: Mathematical models Type: general – SubjectFull: Robots Type: general Titles: – TitleFull: A general architecture of oritatami systems for simulating arbitrary finite automata. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Han, Yo-Sub – PersonEntity: Name: NameFull: Kim, Hwee – PersonEntity: Name: NameFull: Masuda, Yusei – PersonEntity: Name: NameFull: Seki, Shinnosuke IsPartOfRelationships: – BibEntity: Dates: – D: 16 M: 05 Text: May2021 Type: published Y: 2021 Identifiers: – Type: issn-print Value: 03043975 Numbering: – Type: volume Value: 870 Titles: – TitleFull: Theoretical Computer Science Type: main |
| ResultId | 1 |
