A general architecture of oritatami systems for simulating arbitrary finite automata

Autor: Shinnosuke Seki, Yo-Sub Han, Yusei Masuda, Hwee Kim
Rok vydání: 2021
Předmět:
FOS: Computer and information sciences
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Discrete Mathematics (cs.DM)
General Computer Science
Formal Languages and Automata Theory (cs.FL)
Computer science
Computer Science - Formal Languages and Automata Theory
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Set (abstract data type)
Turing machine
symbols.namesake
0202 electrical engineering
electronic engineering
information engineering
Nondeterministic finite automaton
Discrete mathematics
Finite-state machine
Order (ring theory)
Folding (DSP implementation)
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
010201 computation theory & mathematics
symbols
020201 artificial intelligence & image processing
State (computer science)
Alphabet
Computer Science::Formal Languages and Automata Theory
Word (computer architecture)
Computer Science - Discrete Mathematics
Zdroj: Theoretical Computer Science. 870:29-52
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2020.12.014
Popis: 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 Σ.
Databáze: OpenAIRE
Externí odkaz: