The Relations among Watson-Crick Automata and Their Relations with Context-Free Languages(Automata and Formal Language Theory)
スポンサーリンク
概要
- 論文の詳細を見る
Watson-Crick automata were introduced as a new computer model and have been intensively investigated regarding their computational power. In this paper, aiming to establish the relations among language families defined by Watson-Crick automata and the family of context-free languages completely, we obtain the following results. (1) F1WK=FSWK=FWK, (2) FWK=AWK, (3) there exists a language which is not context-free but belongs to NWK, and (4) there exists a context-free language which does not belong to AWK.
- 社団法人電子情報通信学会の論文
- 2006-10-01
著者
-
Hirose Sadaki
Faculty Of Engineering Toyama University
-
Hirose Sadaki
Faculty Of Engineering University Of Toyama
-
Okawa Satoshi
Faculty Of Computer Science And Engineering The University Of Aizu
関連論文
- 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