プール式処理による不完全指定順序機械の最小化

• Item type: Journal(1)
• 公開日: 1990-11-15
• タイトル: プール式処理による不完全指定順序機械の最小化
• タイトル / 言語: en
• タイトル: Minimization of Incompletely Specified Sequential Machines by Boolean Processing
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: ハード基礎理論
• 著者所属: 京都大学工学部情報工学教室
• 著者所属: 京都大学工学部情報工学教室
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者名: 松本, 忍; 矢島, 脩三
• 著者名(英): Shinobu, Matsumoto; Shuzo, Yajima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 不完全指定順序機械の内部状態数を最小化する問題については 従前より様々な解法が研究されてきたが 順序回路の設計自動化という観点から この問題の重要性はむしろ高まっており より優れた解法が求められている.本論文ではこの問題に対して 閉じた被覆の条件を表すプール式(閉被覆関数)に基づいた厳密な最小化のための新しい手法を提案する.厳密解の解法を確立することにより 近似解の評価などにも役立てることができる.最初に 最小の閉じた被覆の解の候補として冗長である両立集合を除去するために 閉被覆関数の包含関係を用いた新しい手法を提案する.この手法は従来提案された同様の手法を概念的に包含しており より強力である.次に プール式の効率的な処理を行う二分決定グラフを用いた汲小の閉じた被覆の選択の手法について述べる.この手法は二分決定グラフのサブグラフの共有によって 探索空間の共有を実現して 論理関数の表現手法である二分決定グラフを組合せ問題に応用するものである.さらに最小解の状想数の上限値に対して考察を行い 新たな上限値の計算法を提案し しきい値関数を用いることによって この上限値を股小解の探索に利用する手法についても述べる.最後に本手法により いくつかの完全指定順序機械の厳密な最小化を行った実験結果を示す.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 31, 号 11, p. 1-9, 発行日 1990-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764