多面体分割を用いた有理数プレスブルガー文真偽判定アルゴリズムとその実装
スポンサーリンク
概要
- 論文の詳細を見る
加算を持つ有理数の理論(有理数変数,有理数定数,+,-,-,く,A,V,V,ヨがらなる理論)の上の冠頭形の閉論理式(PRP文と呼ぶ)の真偽判定ルーチンはプロトコルのテスト,ハードウェアのタイミング検証などに利用される.著者らは最も速いPRP文の真偽判定アルゴリズムよりを既に提案している.本稿では,筆者らが提案したアルゴリズムの多面体分割を用いた高速化法と,その評価についで述べる.高速化法として,次の3点が挙げられる.1.多面体同士を併合し,その結果できる凹多面体も扱えるようにすることで,処理する多面体の数を最小限にする.2.投影の領域を計算する方法を改善し,真偽判定に必要ない多面体を処理する手間を減らす.3.投影の領域を計算する際の凹多面体同士の交差判定の回数を減らす.
- 1999-11-16