文献

J-GLOBAL ID：202202210363779891   整理番号：22A0231461

測度のためのランダム性と初期セグメント複雑性【JST・京大機械翻訳】

Randomness and initial segment complexity for measures

著者 (3件)： Nies Andre (Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand) ,  Stephan Frank (Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, Block S17, Singapore 117690, Republic of Singapore) ,  Stephan Frank (Department of Computer Science, National University of Singapore, 10 Lower Kent Ridge Road, Block S17, Singapore 117690, Republic of Singapore)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 900  ページ： 1-19  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 著者らは,Cantor空間に関する確率測度のためのアルゴリズムランダム性特性を研究した。著者らは,無限ビットシーケンスの空間に関する測度μが,非Martin-Lofランダムビットシーケンスがμに関してヌル集合を形成するならば,絶対に連続するMartin-Lofであった。対策のための弱いランダム性概念としてこれを考察した。例から始め,Solovay試験に関連したロバスト性特性を提供した。長さnにおける測度μの初期セグメント複雑性は,CまたはKのいずれかの意味で,長さnのストリングの記述的複雑性に関するμ平均として定義される。この弱いランダム性の概念を,その初期セグメント複雑性の成長の尺度に関連づける。最大成長は弱いランダム性特性を意味するが,Levin-Schnorr定理の含意も失敗することを示した。測度のC自明性とK自明度を議論し,これら2つの概念を互いに関係づける。ここで,自明さは,初期セグメント複雑性ができるだけゆっくり成長することを意味する。HoyrupとRojasの意味におけるMartin-Lofランダムであるすべての測度は,Martin-Lof絶対連続であることを示した。後者の特性だけが原子と互換性があるので,逆に失敗した。最終セクションでは,一般的なエルゴード計算可能な測度に対して弱いランダム性を考慮する。Shannon-McMillan-Breiman定理の適切な有効バージョンとビットシーケンスを測度で置換するBrudno定理を探索した。いくつかの未解決問題で結論を下した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *測度 ,  互換性 ,  確率測度 ,  ロバスト性
準シソーラス用語： *ランダム性 ,  複雑性 ,  未解決問題 , 【Automatic Indexing@JST】

著者キーワード (4件)： Martin-Lofランダム性 ,  対策 ,  初期セグメントの複雑さ ,  K-自明性

分類 (2件)： 計算理論  (JB02000A) ,  システム・制御理論一般  (IA02010H)

タイトルに関連する用語 (5件)： 測度 ,  ランダム性 ,  初期 ,  セグメント ,  複雑性