同時書込みを許すPRAMの計算時間の下限について

• Item type: SIG Technical Reports(1)
• 公開日: 1987-12-10
• タイトル: 同時書込みを許すPRAMの計算時間の下限について
• タイトル / 言語: en
• タイトル: Very Small Tight Bounds on the Time of Uniform PRAMs with Simultaneous Writes
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都産業大学
• 著者所属(英): en
• 著者所属(英): Kyoto Sangyo University
• 著者名: 岩間, 一雄
• 著者名(英): Kazuo, Iwama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: A(i j)をアッカーマン関数とし，A^^-_k(n)をA^^-_k(n) ＝ (A(i j) ≧ nである最小のj)で定義される（A(i j)の逆）関数とする．同時書き込みを許し，演算として＋，?，ビットごとのAND，ビットごとのORの4種を許す並列乱アクセス機械(PRAM)の計算時間の下限に関し，つぎの定理を証明する：任意のc≧4に対し，このようなPRAM（多項式プロセッサ数）によりΘ(A^^-_c(n))ステップで計算される非退化のn変数論理関数が存在する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let A(i,j) be the Ackermann function and let A^^-_k(n) be its inverse function defined by A^^-_k(n) = least j such that A(k,j)＆ｇｅ；n. We prove very small, nonconstant, tight upper (lower) bounds for the computation time of uniform PRAMs with concurrent writes and with operations +, -, bitwise OR and bitwise AN__-D: For any constant c＆ｇｅ；4, there is a nondegenerate Boolean function G_c of n variables such that it takes Θ(A^^-_c(n)) steps to compute G_c by such PRAMs with polynomial number of processors.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10485570
• 書誌情報: 情報処理学会研究報告プログラミング（PRO）; 巻 1987, 号 89(1987-PRO-023), p. 85-94, 発行日 1987-12-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会