In this paper, we propose an architecture of oritatami systems 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(t4 log2 t) steps in order to simulate t steps of a Turing machine. The architecture we propose employs only 329 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 Σ.
|Title of host publication||Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings|
|Editors||Michal Hospodár, Galina Jirásková|
|Number of pages||12|
|Publication status||Published - 2019|
|Event||24th International Conference on Implementation and Application of Automata, CIAA 2019 - Košice, Slovakia|
Duration: 2019 Jul 22 → 2019 Jul 25
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||24th International Conference on Implementation and Application of Automata, CIAA 2019|
|Period||19/7/22 → 19/7/25|
Bibliographical notePublisher Copyright:
© 2019, Springer Nature Switzerland AG.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)