確率リバウンドオートマタについて

• 資料種別: 記事
• タイトル: 確率リバウンドオートマタについて
• 著者標目: 張 嵐; 岡崎 世雄; 井上 克司; 伊藤 暁; 王 躍
• 出版年月日等: 1997-11-14
• 出版年（W3CDTF）: 1997-11-14
• タイトル（掲載誌）: 電子情報通信学会技術研究報告. COMP, コンピュテーション
• 巻号年月日等（掲載誌）: 97 375
• 掲載巻: 97
• 掲載号: 375
• 掲載ページ: 89-96
• 掲載年月日（W3CDTF）: 1997-11-14
• 出版事項（掲載誌）: 一般社団法人電子情報通信学会
• 本文の言語コード: en
• 件名標目: 確率リバウンドオートマトン; 1マーカリバウンドオートマトン; 非決定性2方向1カウンタオートマトン; 文脈自由言語; 閉包性; probabilistic rebound automaton; one-marker rebound automaton; two-way nondeterministic one counter automaton; context-free language; closure property
• 対象利用者: 一般
• 連携機関・データベース: 国立情報学研究所 : CiNii Research; https://cir.nii.ac.jp/
• 提供元機関・データベース: CiNii Articles
• NII論文ID: 110003191324

• 要約等: 確率リバウンドオートマトン(PRA)を導入し、その受理能力と閉包性について考察する。1/2より小さい誤り確率を持つPRA'sによって認識される言語のクラスをL[PRA]と記すとき、以下のことが成り立つことを示す。(1)L[PRA]は文脈自由言語族と比較不能である。(2)非決定性2方向1カウンタオート...