確率リバウンドオートマタについて
書誌事項
- タイトル別名
-
- A Note on Probabilistic Rebound Automata
この論文をさがす
説明
確率リバウンドオートマトン(PRA)を導入し、その受理能力と閉包性について考察する。1/2より小さい誤り確率を持つPRA'sによって認識される言語のクラスをL[PRA]と記すとき、以下のことが成り立つことを示す。(1)L[PRA]は文脈自由言語族と比較不能である。(2)非決定性2方向1カウンタオートマトンによっては受理されるが、L[PRA]には含まれない言語が存在する。(3)決定性1マーカリバウンドオートマトンによっては受理されるが、L[PRA]には含まれない言語が存在する。(4)L[PRA]は連接、kleene+演算に関し閉じていない。
This paper introduces a probabilistic rebound automaton(PRA), and investigates its accepting power and closure property. We show that (1) the class of languages recognized by PRA's with error probability less than 1/2, L[PRA], is incomparable with the class of context-free languages, (2) there is a language accepted by a two-way nondeterministic one counter automaton, but not in L[PRA], and (3) there is a language accepted by a deterministic one-marker rebound automaton, but not in L[PRA]. We also show that L[PRA] is not closed under concatenation and Kleene +.
収録刊行物
-
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
-
電子情報通信学会技術研究報告. COMP, コンピュテーション 97 (375), 89-96, 1997-11-14
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1570854177376769152
-
- NII論文ID
- 110003191324
-
- NII書誌ID
- AN10013152
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles
