| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-09-03 11:20 Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages -- (Preliminary Version) -- ○Tomoyuki Yamakami（Univ. of Fukui）  COMP2013-27 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | We impose various oracle mechanisms on nondeterministic pushdown automata, which naturally induce nondeterministic reducibilities among formal languages in a theory of context-free languages. In particular, we examine a notion of nondeterministic many-one CFL-reducibility and conduct a ground work to formulate a coherent framework for further expositions. Two more powerful reducibilities--bounded truth-table and Turing CFL-reducibilities--are also discussed in comparison. The Turing CFL-reducibility, in particular, makes it possible to induce a useful hierarchy (the CFL hierarchy) built over the family CFL of context-free languages. For each level of this hierarchy, basic structural properties are proven and three alternative characterizations are presented. The first and second levels of the hierarchy are proven to be different. The rest of the hierarchy is also infinite unless the polynomial hierarchy over NP collapses. This follows from a characterization of the Boolean hierarchy over the k-th level of the polynomial hierarchy in terms of the Boolean hierarchy over the k+1-st level of the CFL hierarchy. We argue that the CFL hierarchy coincides with a hierarchy over CFL built by applications of many-one CFL-reductions. Moreover, we exhibit a relativized world where BPCFL--a bounded-error probabilistic version of CFL--is not located within the second level of the CFL hierarchy. |
|
| キーワード | （和） | / / / / / / / |
| （英） | regular language / context-free language / pushdown automaton / oracle / many-one reducibility / Turing reducibility / truth-table reducibility / CFL hierarchy | |
| 文献情報 | 信学技報, vol. 113, no. 198, COMP2013-27, pp. 17-24, 2013年9月. | |
| 資料番号 | COMP2013-27 | |
| 発行日 | 2013-08-27 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2013-27 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2013-09-03 - 2013-09-03 |
| 開催地（和） | 鳥取環境大学 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2013-09-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages |
| サブタイトル（英） | (Preliminary Version) |
| キーワード(1)（和/英） | / regular language |
| キーワード(2)（和/英） | / context-free language |
| キーワード(3)（和/英） | / pushdown automaton |
| キーワード(4)（和/英） | / oracle |
| キーワード(5)（和/英） | / many-one reducibility |
| キーワード(6)（和/英） | / Turing reducibility |
| キーワード(7)（和/英） | / truth-table reducibility |
| キーワード(8)（和/英） | / CFL hierarchy |
| 第1著者 氏名（和/英/ヨミ） | Tomoyuki Yamakami / Tomoyuki Yamakami / |
| 第1著者 所属（和/英） | University of Fukui (略称： 福井大) University of Fukui (略称： Univ. of Fukui) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-09-03 11:20:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2013-27 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.198 |
| ページ範囲 | pp.17-24 |
| ページ数 | 8 |
| 発行日 | 2013-08-27 (COMP) |
[研究会発表申込システムのトップページに戻る]