%0 Conference Proceedings
%T Self-attraction Removal from Oritatami Systems
%+ Yonsei University
%+ University of Central Arkansas (UCA)
%+ University of Electro-Communications [Tokyo] (UEC)
%A Han, Yo-Sub
%A Kim, Hwee
%A Rogers, Trent, A.
%A Seki, Shinnosuke
%Z Part 2: Contributed Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 19th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Milano, Italy
%Y Giovanni Pighizzini
%Y Cezar Câmpeanu
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10316
%P 164-176
%8 2017-07-03
%D 2017
%R 10.1007/978-3-319-60252-3_13
%Z Computer Science [cs]Conference papers
%X RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized (transcribed). Oritatami is a computational model of this phenomenon, which lets its transcript, a sequence of beads (abstract molecules) fold cotranscriptionally via interactions between beads according to its ruleset. In this paper, we study the problem of removing self-attractions, which lets a bead interact with another bead of the same kind, from a given oritatami system without changing its behavior. We provide an algorithm for that with overhead linear in the delay parameter, which should be considerably smaller than the length of its transcript. We also show that this overhead is tight.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01657016/document
%2 https://inria.hal.science/hal-01657016/file/440206_1_En_13_Chapter.pdf
%L hal-01657016
%U https://inria.hal.science/hal-01657016
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10316