二分決定グラフとチューリング機械と組合せ論理回路の関係について

• Item type: SIG Technical Reports(1)
• 公開日: 1992-11-20
• タイトル: 二分決定グラフとチューリング機械と組合せ論理回路の関係について
• タイトル / 言語: en
• タイトル: On the Relations between Binary Decision Diagrams, Turing Machines and Combinational Logic Circuits
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学工学部情報工学教室
• 著者所属: 京都大学工学部情報工学教室
• 著者所属: 京都大学工学部情報工学教室
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者名: 澤田, 宏; 武永, 康彦; 矢島, 脩三
• 著者名(英): Hiroshi, Sawada; Yasuhiko, Takenaga; Shuzo, Yajima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ある論理関数を表現する二分決定グラフは，入力変数の順序を変更することでその大きさが変化する．我々は，入力変数の順序づけを考慮した場合の，二分決定グラフの表現能力について議論する．そのため，入力テープの内容を並び替える機械を別に持つオンラインチューリング機械を定義し，二分決定グラフとの関係を明らかにする，また，セレタタのみで構成される回路を定義し，二分決定グラフとの関係について考える．さらに，平面回路と二分決定グラフの関係についても考える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The size of the Binary Decision Diagram which represents a Boolean function depends on the ordering of input variables. We discuss the expressible power of Binary Decision Diagrams considering the ordering of input variables. For this purpose, we define a on-line Turing machine with an input ordering machine and clarify the relation between Binary Decision Diagrams. We also define a circuit which consists only of selectors and discuss the relation between Binary Decision Diagrams. Furthermore, the relation between Binary Decision Diagrams and planar circuits is discussed.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1992, 号 94(1992-AL-030), p. 171-178, 発行日 1992-11-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会