On Computational Power of Insertion-Deletion Systems without Using Contexts(Automata and Formal Language Theory)
スポンサーリンク
概要
- 論文の詳細を見る
An Insertion-Deletion system, first introduced in [1], is a theoretical computing model in the DNA computing framework based on insertion and deletion operations. When insertion and deletion operations work together, as expected, they are very powerful. In fact, it has been shown that even the very restricted Insertion-Deletion systems can characterize the class of recursively enumerable languages [1]-[4]. In this paper, we investigate the computational power of Insertion-Deletion systems and show that they preserve the computational universality without using contexts.
- 社団法人電子情報通信学会の論文
- 2005-08-01
著者
-
HIROSE Sadaki
Faculty of Engineering, Toyama University
-
Hirose Sadaki
Faculty Of Engineering Toyama University
-
Okawa Satoshi
Faculty Of Computer Science And Engineering The University Of Aizu
-
Okawa Satoshi
Univ. Aizu Aizu‐wakamatsu‐shi Jpn
関連論文
- Control Methods of Genetic Algorithms under Changing Environments
- High Speed Hypothetical Reasoning System with Case-Based Reasoning for Diagnosing Faults
- Some Relations between Watson-Crick Finite Automata and Chomsky Hierarchy(Automata and Formal Language Theory)
- On Computational Power of Insertion-Deletion Systems without Using Contexts(Automata and Formal Language Theory)
- Upper Bounds of the Correlation Functions of a Class of Binary Zero-Correlation-Zone Sequences(Coding Theory)
- The Firing Squad Synchronization Problems for Number Patterns on a Seven-Segment Display and Segment Arrays
- The Relations among Watson-Crick Automata and Their Relations with Context-Free Languages(Automata and Formal Language Theory)
- Correction to the Diameter of Trivalent Cayley Graphs (Special Section on Discrete Mathematics and Its Applications)
- A Class of Ternary Sequence Sets with a Zero-Correlation Zone(Coding Theory)
- A Ternary Zero-Correlation Zone Sequence Set Having Wide Inter-Subset Zero-Correlation Zone