文献

J-GLOBAL ID：201702268965410196   整理番号：17A1185927

タイル自己集合における濃度に依存しない乱数発生【Powered by NICT】

Concentration independent random number generation in tile self-assembly

著者 (5件)： Chalk Cameron T. (Department of Computer Science, The University of Texas - Rio Grande Valley, Edinburg, TX, 78539-2999, United States) ,  Fu Bin (Department of Computer Science, The University of Texas - Rio Grande Valley, Edinburg, TX, 78539-2999, United States) ,  Martinez Eric (Department of Computer Science, The University of Texas - Rio Grande Valley, Edinburg, TX, 78539-2999, United States) ,  Schweller Robert (Department of Computer Science, The University of Texas - Rio Grande Valley, Edinburg, TX, 78539-2999, United States) ,  Wylie Tim (Department of Computer Science, The University of Texas - Rio Grande Valley, Edinburg, TX, 78539-2999, United States)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 667  ページ： 1-15  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,ゴールは,システムの結果としての集合体は,確率1/Nと各分割内にあり,系におけるタイルタイプの相対的濃度割当に関係なくようにその末端集合体はn分割に分割できる抽象タイル組立システム(aTAMシステム)を設計することであるがロバストな乱数生成問題を導入した。最初に,これはaTAM内2が可能である(ロバスト公正なコインフリップ),およびそのようなシステムは,最悪の場合O(1)空間利用を保証することを示した。空間複雑さ,初期種子サイズ,温度,タイル複雑性,バイアス,拡張性におけるトレードオフを示す変異体を主要建築を伴うと,いくつかの否定的結果を証明した。応用として,Chandran,Gopalkrishnan,Reifの結果と著者らのコインフリップシステムを組み合わせて任意の正の整数n,はどの濃度割当のための期待される長さnの一定幅線形集合を生成するO(logn)タイルシステムが存在することを示した。,ロバストな公平なコインフリップ結果すべてaTAMにおけるロバストな乱数発生の問題を解くために拡張した。ロバストなランダムビット発生溶液の二変異体を提示した:非有界空間解と小さなバイアスを招く有界空間解。さらに,タイル濃度は各集合段階で任意に変化する硬いシナリオを考察し,これがaTAM不可能であるが,問題は,文献からのエキゾチックタイルアセンブリモデルによって解くことができることを示した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： ロバスト性 ,  バイアス ,  *自己集合 ,  線形性 ,  *乱数発生 ,  凝集体
準シソーラス用語： 有界 ,  複雑性 , 【Automatic Indexing@JST】

著者キーワード (5件)： タイル自己集合 ,  aTAM ,  DNA計算 ,  バイオコンピューティング ,  ランダム化

分類 (1件)： 符号理論  (ND02030R)

タイトルに関連する用語 (3件)： タイル ,  自己集合 ,  乱数発生