Real-Time Recognition of Cyclic Strings by One-Way and Two-way Cellular Automata(<Special Section>Foundations of Computer Science)
スポンサーリンク
概要
- 論文の詳細を見る
This paper discusses real-time language recognition by 1-dimensional one-way cellular automata (OCAs) and two-way cellular automata (Cas), focusing on limitations of the parallel computation power To clarify the limitations, we investigate real-time recognition of cyclic strings of the form u^k with u ∈ {0,1}^+ and k ≥ 2 We show a version of pumping lemma for recognizing cyclic strings by OCAs, which can be used for proving that several languages are not recognizable by OCAs in real time The paper also discusses the real-time language recognition of Cas by prefix and postfix computation, in which every prefix or postfix of an input string is also accepted, if the prefix or postfix is in the language It is shown that there are languages L ⊆ Σ^+ such that L is not recognizable by OCA in real-time and the reversal of L and the concatenation LΣ^* are recognizable by CA in real-time.
- 社団法人電子情報通信学会の論文
- 2005-01-01
著者
-
Nakamura Katsuhiko
Department Of Cardiovascular Surgery Omura Municipal Hospital Cardiovascular Center
-
Nakamura Katsuhiko
Department Of Computers And Systems Engineering College Of Science And Engineering Tokyo Denki Unive
関連論文
- A New Hydrocolloid Dressing Prevents Surgical Site Infection of Median Sternotomy Wounds
- Off-pump CABG for a Patient with a Brain Tumor
- 0074 OXIDATIVE STRESS DURING RETROG-RADE WARM AND COLD CONTINUOUS BLOOD CARDIOPLEGIA FOR CORONARY ARTERY BYPASS SURGERY.
- Coronary artery bypass grafting in patients with pulmonary aspergillosis
- Real-Time Recognition of Cyclic Strings by One-Way and Two-way Cellular Automata(Foundations of Computer Science)
- Gum chewing enhances early recovery of bowel function following transperitoneal abdominal aortic surgery