論理関数表現のモデルとシンボリックアルゴリズム

逻辑函数表达式模型和符号算法

• 批准号: 16092207
• 负责人: 武永 康彦
• 金额: $ 7.17万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16092207/
• 关键词: 論理関数; アルゴリズム; 二分決定グラフ; シンボリックアルゴリズム; パラメータ化計算量; グラフアルゴリズム; Tree-shellable論理関数; 二分モーメントグラフ; Tree-Shellable論理関数; 区間グラフ

1.二分決定グラフによるデータ表現については、第一に、二分決定グラフの構造を論理関数で表現する二分決定グラフの非明示的表現を用いて、効率的な表現が可能な論理関数について研究を行ない、多変量閾値関数を入力変数のビット長に依存しないサイズで表現できることを示した。第二に、A07班山下との共同研究により、量子論理関数を効率よく表現するためのOBDDの変種データ構造を比較検討し、山下が以前に提案したDecisionDiagrams for Matrix Functions(DDMFs)の有効性を理論的に考察した。このデータ構造が、量子論理回路に特有の制約条件をうまく利用しており、単純なOBDDよりも一層データを圧縮し、処理効率を高めていることを明らかにした。2.OBDDに基づくシンボリックアルゴリズムについては、前年度に引き続き、トポロジカルソートの列挙、OBDDによる画像処理アルゴリズムについて研究を行なった。前者では先行頂点数等を求めることにより従来法より計算過程でのOBDDサイズを大幅に抑えられることを示した。後者ではOBDD予測符号化を用いることによりOBDDサイズが圧縮可能であり、提案済みの画像処理アルゴリズムをほぼそのまま利用できることを示した。また、OBDDを用いたナンバーリンクの解法、問題の正当性の判定手法の提案・実装を行なった。

1. It is possible to determine the number of data that is not explicitly indicated in the table that is not expressly used. It is possible to analyze the number of data that is not explicitly expressed. The second class and Class A07 Yamashita jointly studied the theory of physics and quantum chemistry. The results showed that several kinds of OBDD were built and compared with each other. The previous proposal of Yamashita proposed the review of the theory of DecisionDiagrams for Matrix Functions (DDMFs). There are many unique conditions in the process of building and quantum loops, such as the use of OBDD, the higher the efficiency, the higher the efficiency, and the higher the efficiency. 2.OBDD

项目成果

多変量〓値関数の非明示的OBDD表現

多元值函数的隐式 OBDD 表示

• 发表时间: 2008
• 作者: Shin-ichi Nakayama;shigeru Masuyama;中山 昌光
• 通讯作者: 中山 昌光

OBDDを用いた画像処理アルゴリズム

使用OBDD的图像处理算法

• 发表时间: 2008
• 作者: 渡辺哲也;大内進;金子健;山口俊光;下条誠;島田茂伸;番能 孝生
• 通讯作者: 番能 孝生

Vertex Coloring of Comparability+ke and -ke Graphs

可比性 ke 和 -ke 图的顶点着色

• 发表时间: 2007
• 期刊: Lecture Note in Computer Science (WG'06) 4271
• 作者: Y.Takenaga;K.Higashide
• 通讯作者: K.Higashide

組合せ最適化問題としてのぷよぷよの連鎖数判定問題

Puyo Puyo 链数确定问题作为组合优化问题

• 发表时间: 2006
• 期刊: 電子情報通信学会論文誌 J89-D,3
• 作者: Y.Takenaga;T.Walsh;松金輝久
• 通讯作者: 松金輝久

TVee-Shellability of Restricted DNFs

受限 DNF 的 TVee 可脱壳性

• 发表时间: 2008
• 期刊: IEICE Trans. In£& Syst. E-91D
• 作者: S. Imahori;M. Yagiura;H. Nagamochi;杉原厚吉;杉原厚吉;YasiiMko Takenaga
• 通讯作者: YasiiMko Takenaga