(13) 集合制約ソルバー

［中間報告］

(１) 研究進捗状況

集合制約ソルバーの機能の内、最もプリミティブなもの、すなわち 論理機能を含まない制約に対するソルバーは、要素変数ソルバー の部分を除いて確定したが、要素変数ソルバーについては引続き 検討中。グレブナ基底に関するプログラムの改良については、アル ゴリズムが改良(高速化)できることが判明したので、現在そのイン プリメントをおこなっている。

(２) 現在までの主な成果

• 集合ブール環を係数ブールとするブール多項式環上のグレブナ基底、 及び、集合ブール環上のブール多項式環を係数ブールとするブール 多項式環上のグレブナ基底を求めるプログラムが一応完成した。 (ただしアルゴリズムが改良(高速化)できることが判明したので、 改良中。)
• 拡張定理に基ずく変数消去アルゴリズムをインプリメントした。
• comprehensiveグレブナ基底を求めるアルゴリズム及び、それに関す る重要定理を使った一般化されたリダクションのプログラムを作成 した
• 集合制約からブール多項式環の連立方程式へと変換するプログラム は完成した。

(３) 今後の研究概要

要素変数ソルバーは、グレブナ基底と並んで集合制約ソルバーの 主要エンジンとなるものであるが、アルゴリズムの理論的検討は完成 しておらず、引続きいろいろな方針の検討(場合によってはインプリ メントを行って比較しなければならない)が必要である。 どういったソルバーをどのような形態でパッケージとして用意するか も重要な検討課題である。

(４) 今年度目標成果

• より高速化されたグレブナ基底の計算アルゴリズムがインプリメントされる。
• 高速化されたグレブナ基底計算を利用した集合制約ソルバーが完成される。
• 外部プログラムにリンクして使用するための、インターフェースの作成。その実現のための種々のソルバーパッケージの制作。