このアイテムのアクセス数: 229
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| s00224-013-9506-8.pdf | 218.32 kB | Adobe PDF | 見る/開く |
| タイトル: | Schnorr Triviality and Its Equivalent Notions |
| 著者: | Miyabe, Kenshi |
| 著者名の別形: | 宮部, 賢志 |
| キーワード: | Algorithmic randomness Schnorr randomness Schnorr triviality Uniform relativization |
| 発行日: | 29-Sep-2013 |
| 出版者: | Springer US |
| 誌名: | Theory of Computing Systems |
| 巻: | 56 |
| 号: | 3 |
| 開始ページ: | 465 |
| 終了ページ: | 486 |
| 抄録: | We give some characterizations of Schnorr triviality. In concrete terms, we introduce a reducibility related to decidable prefix-free machines and show the equivalence with Schnorr reducibility. We also give a uniform-Schnorr-randomness version of the equivalence of LR-reducibility and LK-reducibility. Finally we prove a base-type characterization of Schnorr triviality. |
| 著作権等: | The final publication is available at Springer via http://dx.doi.org/10.1007/s00224-013-9506-8 この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
| URI: | http://hdl.handle.net/2433/198571 |
| DOI(出版社版): | 10.1007/s00224-013-9506-8 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。