数理解析研究所講究録920 巻 1995 年 53-61

53

6.1 はじめに
ブ $-$ , 環$\mathrm{B}$を係数環とする多項式環$\mathrm{B}[X_{1}, \ldots, X_{n}]$項式による単項リダクションが定義され, これを用いてにおいて, 7-) 環固有の性質を使って多$\mathrm{B}[X_{1}, \ldots, X_{n}]$におけるグレブナー基底がBuchberger のアルゴリズムと同様の完備化手続きに基づくアルゴリズムによって求めることができる.([Sakai) 本稿ではこのグレブナー基底が持ついくつかの性質について紹$88,90],[\mathrm{w}_{\mathrm{e}}\mathrm{i}\mathrm{s}\mathrm{p}\mathrm{f}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}8\mathrm{g}]$介する. 以下ではまず 2 節で$\mathrm{B}[X_{1}, \ldots, X_{n}]$における単項リダクションとグレブナー基底について概説する. 次に 3 節で syzygy 基底との関係とアルゴリズムの効率化,4 節で comprehensive グレブナー

基底の構成について述べ,5 節で集合制約ソルバーへの応用を紹介する.

6.2 ブーリアン
単位元 1 を持つ可換環$\mathrm{B}$

グレブナー基底はすべての元がベキ等元になるとき, すなわち
$a^{2}=a$$\forall a\in \mathrm{B}$.

をみたすとき, 7–) 環と呼ばれ, 次の性質を持つ.

$\forall a\in \mathrm{B}$$a+a=0$ .

54

以下では, 与えられた-7-) 環を表す文字として $a,$
$>$

$b,$

$c,$

$\ldots$を,を係数環とする多項式環$\mathrm{B}$$x_{\iota},$$x_{2},$$X_{\hslash}$$\ldots,$を考える.

$\mathrm{B}[x_{1}, x_{2}, \ldots, x_{\hslash}]$からなる項を表す文字として\alpha ,$\beta,$$\gamma,$$\ldots$$\mathrm{B}$

の要素

を使う.

をアドミシブ) な全順序 (admissible ordering), すなわち

1.

$\alpha>\beta$

ならば任意の項\mbox{\boldmath $\gamma$} にたいして\alpha \mbox{\boldmath $\gamma$}$>\beta\gamma-\vee\cdot$

2. 1 と異なる任意の項\alpha にたいして\alpha $>1$ .
が成り立つとする.

多項式 の順序最大の項 (最大項) を $l_{PP}(f)$ で, その係数を$f$$lc(f)(\epsilon \mathrm{B})$で, さらに $f$ からその最大単項すなわち $lc(f)lpp(f)$ を取り除いた残りの部分を $reS(f)$ でそれぞれ表す.

多項式 にたいし, $lc(f)=a,lpP(f)=\alpha,res(f)=h$ であるとき,
$f$

多項式

$f=a\alpha\triangleright h$

$f$

を記号

$a\alpha\triangleright h$で表すものとする.

による多項式上の単項リダクション (M-reduction, 以下では単にリダクションと呼ぶ)\rightarrow f を以下のように定義する.
$b\alpha\gamma+garrow f(1+a)b\alpha\gamma+abh\gamma+g$

ただし, ここで多項式辺に$a$$b\alpha\gamma+\mathit{9}$は $ab\neq 0$ をみたすものに限定する.

.
(注意. $f=0$ なら $a\alpha=h$ , 両をかけると $a\alpha=$ 晶となる. また -7-) 環では-(マイナス) は扱わないが, 仮に一を用いれば$a+a=0$ より $(1+a)=(1-a)$ となるが, この形にすると上式の意味は明白であろう.)$F$

を多項式の集合とする.

ンすなわちによるリダクション $arrow F$ を $F$ に含まれるあるルールによるリダクショ$harrow Fh’\Leftrightarrow\exists f\in Fharrow fh’$

集合のとき

$arrow F$

で定義する.

の既約形は–般には–つ以上存在するが$G$の推移反射閉包を$arrow F$で表す. F が有限は停止性を持つ, すなわち無限に続く多項式のリダクション $foarrow Ff1arrow Ff_{2}\cdot$ , . は存の任意の要素でリダクションできないとき, g は$I$$arrow F$(無限集合の場合には\rightarrow F は–般に停止性は持たない.) 多項式 $f$ と g が $farrow Fg$ かつ

在しない.
$F$

$F$

$f\downarrow F$$f$の $arrow F$ による既約形であるという.

$arrow F$$g$はによる $f$

でそのうちの–つを表す.

を $\mathrm{B}[X_{1}, X_{2}, \ldots, X_{n}]$ のイデアルとする. ルール多項式の有限集合 $G$ が以下の性質をみたすとき,は I のブーリアングレブナー基底と呼ばれる.

1. I は$G$で生成されるイデアルである.

2. $g+g’\in I$$\Leftrightarrow$(特に $g\in I$

多項式

$f$

と

$g$

$\mathrm{s}\mathrm{p}(f, g)$

.

ある多項式
$\Leftrightarrow$$garrow$$h$が存在して $garrow ch$ かつ $g’arrow ch$ が成り立つ.

$c0.$ )にたいし以下で定義される多項式を$=lc(g) \frac{lp\mathrm{p}(\mathit{9})}{\mathrm{G}\mathrm{C}\mathrm{D}(l\nu p\mathrm{t}f),lpp(g))}f+$

ここで$\mathrm{G}\mathrm{C}\mathrm{D}(\iota_{P}p(f), l_{P}p(g))$

多項式

$h$

$f$

と gの

$\mathrm{S}$多項式と呼び$\mathrm{s}\mathrm{p}(f, g)$と表す.

$l \mathrm{c}(f)\frac{lp\mathrm{p}(f)}{\mathrm{G}\mathrm{C}\mathrm{D}(l\mathrm{p}\mathrm{P}(f),(\mathrm{P}P(g))}g$

は項 $l_{PP}(f)$ と $lpp(g)$ の最大公約項を表す.

にたいし以下で定義される多項式をその自己$\mathrm{C}$多項式と呼び$\mathrm{s}\mathrm{c}\mathrm{p}(h)$で表す.

$\mathrm{s}\mathrm{c}\mathrm{p}(h)=(1+^{\iota}c(h))h$

ブーリアングレブナー基底は次のように特徴付けられる.
定理 1て多項式の有限集合$\mathrm{s}\mathrm{c}\mathrm{p}(f)arrow c0$

および

$G$

は,

$\mathrm{s}\mathrm{p}(f, g)arrow c0$$\mathrm{G}\mathrm{C}\mathrm{D}(\iota pP(f), l_{PP}(g))\neq 1$

なる任意の多項式 $f,$ $g\in G$ にたいしが成り立つとき, かつそのときに限りブーリアングレブナー

55

基底になる.

ロ

与えられた多項式の有限集合 $F$ にたいし,$F$で生成されるイデアルの-7 一リアングレブナー基底を求めるアルゴリズムは以下のように与えられる.

input $Earrow-F,R-\emptyset$
while$E\neq\emptyset$choose $h\in E$

if$h\downarrow_{R}=0$

then$E-E-\{h\}$else let $f=h\downarrow R$ and$E-(E-\{h\})\cup \mathrm{t}\mathrm{S}\mathrm{c}\mathrm{p}(f)\}\cup$$\{\mathrm{s}\mathrm{p}(\iota_{c(}f)f,$$g)|g\in R$, $\mathrm{G}\mathrm{C}\mathrm{D}(lpp(f), lpp(g))\neq 1\}$
$R-R\cup\{lC(f)f\}$

end-ifend-while

output$R$

R が求めるブーリアングレブナー基底である.

6.3 syzygy 基底とアルゴリズムの効率化
個の単項の列$m$$m$個の多項式の列

でないもの$h_{l_{1}},$$M=(a_{1} \alpha_{1}, a_{2}\alpha_{2}, \ldots, a_{m}\alpha_{m})\#_{\sim}^{}\lambda\backslash \iota \text{し}\sum_{=}.\cdot mh::\iota^{a\alpha_{i}}=0$$(h_{1}, h_{2} , .

$\ldots,$$h_{l_{k}}$.

.

, h_{m})$となるようなを $M$ の syzygy と呼ぶ. 特に, すべての

$h_{:}$

が単項で, そのうち$0$に対して, $lpp(h_{l_{1}}.)\alpha_{l_{1}}=\cdots=lpp(hl_{k})\alpha\iota_{k}$ が成り立つとき, homogeneous

な syzygy と呼ぶ. $M$ の syzygy め全体は明らかにモデュ, を形成するが, これを$-’\downarrow$$S_{M}$

で表す.

通常のグレナー基底の場合と同様に syzygy のことばで定理 1 は次のように–般化することがで
きる.

定理 2
列べたもの,
して$G=\mathrm{t}\mathit{9}1,$$L$$\ldots,$ $g_{m}$} を多項式の有限集合,$M$

を $G$ のすべての要素の最大単項をこの順に

を $S_{M}$ の homogeneous な基底とする. このとき,$\sum_{=1}^{m}.h\dot{.}g_{i}arrow c\backslash 0$が成り立つとき, かつそのときに限り

$G$

$L$

のあらゆる元$(h_{1}$,.

..,$h_{m})$にたいはブーリアングレプナー基底になる.

口

これが実際に–般化になっているのは次のことからみることができる.
$m(>2)$ 個の単項の列 $(a_{1}\alpha_{1}, \ldots, a_{m}\alpha_{m})$ を $M$ とおく. $1\leq i<i<k\leq m$ なる自然数 $i,j,$
いし

$k$

にた

56

$\alpha_{ij}=\mathrm{L}\mathrm{C}\mathrm{M}(\alpha.\cdot, \alpha j)$,$\alpha_{jk}.=$LCM$(\alpha|, \alpha_{j}, \alpha_{k})$,とおく. ここで LCM は最小公倍項を表す. さらに$C:j= \frac{a_{j}\alpha_{j}}{\alpha}.\cdot.\cdot e\sim.\cdot+\frac{a.\alpha_{j}}{\alpha_{j}}.\cdot e_{\mathrm{j}}\sim$

とおく. ここで e\tilde |. は
定理 3

$i$

番目の成分が 1 で残りの成分は,$C.\cdot=(1+a.\cdot)earrow.\cdot$$0$,であるような $m$ 個の列を表す.

$L=\{C_{ij}|1\leq i<i\leq m\}\cup\{C_{i}|1\leq i\leq m\}$

とおくと,

$L$

は $S_{M}$ の homogeneous な

基底になる

口

多項式の集合$F$(適当に列べられているとする) にたいする

syzygy 全体から成るモデュールの基底の元とき,Buchberger によって与えられた$\mathrm{S}$$F$$\mathrm{S}$多項式は, 通常は $F$ の単項の列のの内積として定義される.

例えば係数環が体のと多項式はモデュールの基底として Tayler 基底を用いたもので,これの特殊なケースにあたる.
$m$個の多項式の列$(a_{1}\alpha_{1}\triangleright h1, \ldots, am\alpha_{mm}\triangleright h)$の記号を使うと $F$ . Ci と表され, 通常の$\mathrm{S}$を $F$ とおく. このとき,$a.\alpha|\triangleright h_{i}$の自己$\mathrm{C}$多項式は, 上多項式の –種であることがわかる.

さて homogeneous な基底に関して次のことが成り立つ.

定理 4$1\leq k\leq l$が成り立つとき,(ここで記号

なるあらゆる. は $C_{in_{1}},$$C_{j}.\cdot$$ci\mathfrak{n}_{2}$

)

$k$

に

$\ldots,$$_{}- \text{いし}\alpha_{\mathfrak{n}_{k}}|\alpha:j$であり, さらに$C:n_{1}’ c_{\mathrm{j}}\mathfrak{n}\iota’ cj\mathfrak{n}2’\ldots,$$\mathrm{S}$を多項式の有限集合とする.

input $E-F,R-\emptyset$$E\neq\emptyset$choose $h\in E$
if$h\downarrow_{R}=^{\mathrm{o}}$then$E-E-\{h\}$else let$f=h\downarrow R$

and$E-(E-\{h\})\cup\{_{\mathrm{S}\mathrm{c}_{\mathrm{P}}}(f)\}\cup$$\{\mathrm{c}\mathrm{p}(lc(f)f, g)|g\in R, \neg \mathrm{R}\mathrm{e}\mathrm{d}(f, g)R)\}$$R-R\cup\{lC(f)f\}$

end-ifend-while
output$R$$c_{j}$

直線形和として表される.
口

多項式の計算を除去することによって, ブーリアングレブナー基底を求める

アルゴリズムを, 次のように改良できる.

while$C_{j}n_{l}’ C:,$垢 7-) 代数の和を表す. すなわち $a\vee b=a+b+ab.$ )これにより不要な$F$$(a_{n_{1}n_{2}}\mathrm{v}a\cdots an\downarrow)a:a_{j}=a.a_{j}$57

R は $F$ で生成されるイデアルのブーリアン・グレブナー基底になる.

Red $(f, g, R)$ は不要な$\mathrm{S}$多項式の計算を除去するためのもので, 以下のいずれかの場合に限って真

となる.

場合 1)

$\mathrm{G}\mathrm{C}\mathrm{D}(\iota_{PP}(f), lpp(g))=1$

場合 2) R の中に $lc(f)f$ と$g$;のどちらとも異なる多項式$lpp(h:)|\mathrm{L}\mathrm{C}\mathrm{M}(\iota_{PP}(f), lPp(g))$$h_{1}$, ..

$h_{\{}$があって, それぞれにたいしてが成り立ち, かつ$(lc(h_{1})\cdots lc(h_{l}))\iota C(f)l_{C}(g)=lc(f)lc(g)$となる.

6.4 comprehensive グレブナー基底
多項式環$\mathrm{B}[X\iota,$$x_{2},$$\ldots,$$X_{n}$) はそれ自身\breve 7-) 環にはならないが各変数$X_{1},$$X_{2,\ldots,n}X$をベキ等にすることによって-7–) 環になる. すなわちイデアル $(X_{1}^{2}+X_{1}, X_{2}^{2}+X_{2}, \ldots, X_{n}^{2}+X_{n})$ による剰余環 $\mathrm{B}[X_{1,2}X, \ldots, x_{n}]/$ ( $X_{1}2+X_{1},$ $X_{2}^{2}+X_{2},$$\ldots$, Xn2+X のは再び-7-, 環になる. 以後この 7-) 環

を $\mathrm{B}(X_{1}^{2}+X_{1}, X_{2}^{2}+X_{2}, \ldots, X_{n}^{2}+X_{n})$ で表す.

この剰余環においてもブーリアン・グレブナー基底が自然に導入されるが, 以下では特にことわらない限りブーリアン・グレブナー基底は剰余環上のものを, また剰余環上のリダクションや既約形等の記号も, もとの記号をそのまま使うことにする.

さて剰余環上で考えると comprehensive なグレブナー基底$([\mathrm{w}\mathrm{e}\mathrm{i}_{\mathrm{S}}\mathrm{P}^{\mathrm{f}}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}92])$が容易に構成する

こ・とができることが以下のようにいえる.
$I$を$B(\overline{X},\overline{Y})$の変数呂,$Y_{2},$$\ldots$

上のイデアルとする.
, 玲を表す.

$B(\overline{X})$ともみなすことができる.

$(B(\overline{X}))(\overline{Y})$で表す. このとき$G(\overline{X})$

$n$

このとき

$G(\overline{a})=${$rightarrow-\text{で}\overline{X},\overline{Y}$はそれぞれは 7-) 環なので$(B(\overline{X}))(\overline{Y})$$n$$B(\overline{X},\overline{Y})$個の変数$X_{1},$ $X_{2}$

は係数環を

,...,

$B(\overline{X})$$X_{n}$とにおける I のブーリアン. グレブナ一基底を$I(\overline{a})=\{p(\overline{a},\overline{Y})|P(\overline{X},\overline{Y})\in I\}$$\mathit{9}(\overline{a},\overline{Y})|g(\overline{X},\overline{Y})\in G(\overline{X}\rangle$

and

とおくとこれは$g(\overline{a},\overline{Y})\neq 0$$B(\overline{Y})$$m$個とする剰余環は I の comprehensive ブーリアン・グレブナー基底となる. すなわち個の要素とし,の任意のこ$G(\overline{X})$$\overline{a}$を $B$のイデア) になるが,} とおくと定理 5(1)$G(\overline{a})$は$I(\overline{a})$さらに任意の(2)のブーリアン・グレブナー基底となる.
$f(\overline{X},\overline{Y})\in B(\overline{X},\overline{Y})$にたいして$f(\overline{a},\overline{Y})1c(\overline{a})=(f(\overline{X},\overline{Y})\iota_{G()}\overline{X})(\overline{a},\overline{Y})$が成り立つ.

口

6.5 応用このセクションではブーリアン・グレブナー基底を用いた集合制約ソルバーの実行例をいくつか紹介する. 以下の例では/\ は集合の積八/ は集合の和,1 は補集合を, 小文字 al,$\mathrm{a}2,\ldots$

は集合の要素, 大文

58

字 sl,

$\mathrm{S}2,\ldots,\mathrm{X}1$,X2,. . . は集合を表す.

$?-\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}-\mathrm{s}\mathrm{e}\mathrm{t}-^{\mathrm{e}}1\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}(\mathrm{A}, \mathrm{B}, \mathrm{C})$の Aには集合制約が,$\mathrm{B}$.

には解きたい集合変数$\mathrm{C}$には解きたい集合要素を変数として指定する (指定

されない集合要素はすべて相異なる要素とみなされる). 最初に$\mathrm{C}$が空の実行例を見る.

$?-\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{V}\mathrm{e}-^{\mathrm{s}}\mathrm{e}\mathrm{t}-\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}([$$\{\mathrm{a}1, \mathrm{a}9\}/\backslash (\mathrm{X}2\backslash /\sim_{\mathrm{X}1)=}\{\mathrm{a}2.\mathrm{a}5, \mathrm{a}7\}/\backslash \mathrm{S}5$.

$\mathrm{S}1/\backslash (\mathrm{S}2/\backslash \sim\{\mathrm{a}5\}\backslash /(\mathrm{S}3/\backslash (\mathrm{S}4/\backslash \sim(\mathrm{X}1\backslash /\{\mathrm{a}6\}))))=(\mathrm{S}5/\backslash \mathrm{S}6)\backslash /(\mathrm{S}4/\backslash \mathrm{S}7/\backslash \mathrm{S}2)\backslash /\mathrm{S}8$.

$\mathrm{S}5/\backslash \mathrm{S}4/\backslash \mathrm{S}9/\backslash \mathrm{S}6/\backslash \mathrm{S}2/\backslash (\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}3\backslash /\{\mathrm{a}7\})/\backslash (\{\mathrm{a}9\}\backslash /\mathrm{X}2)=0,$$\mathrm{s}5/\backslash \mathrm{S}8/\backslash \sim(\mathrm{X}3\backslash /\{\mathrm{a}5, \mathrm{a}8\})=0$$\mathrm{S}2/\backslash ("\{\mathrm{a}6, \mathrm{a}8\})=\mathrm{S}4\backslash /\mathrm{S}8.\mathrm{S}2/\backslash (^{\sim}\{\mathrm{a}9\})=\mathrm{S}\mathrm{l}\mathrm{l}\backslash /\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}2\backslash /\{\mathrm{a}5, \mathrm{a}7\}\backslash /\mathrm{S}7,$$\mathrm{S}10/\backslash \mathrm{S}3=0$, S12$=\mathrm{S}9\backslash /\mathrm{S}7,$$\mathrm{S}\mathrm{l}1/\backslash \mathrm{S}3=0$.

$\mathrm{S}9/\backslash \mathrm{S}7/\backslash \mathrm{S}15/\backslash \sim(\mathrm{X}1\backslash /\mathrm{X}2\backslash /\mathrm{X}3\backslash /\{\mathrm{a}4, \mathrm{a}5, \mathrm{a}6, \mathrm{a}7, \mathrm{a}8, \mathrm{a}9,\mathrm{a}\mathrm{l}0\})=0$$\{\mathrm{a}4\}/\backslash \mathrm{S}6=\{\mathrm{a}4\},\mathrm{X}1/\backslash \mathrm{S}9=\mathrm{X}1,$$\mathrm{X}3/\backslash \mathrm{S}7=\mathrm{X}3,$,,$\mathrm{S}1\backslash /\mathrm{S}10\backslash /\mathrm{X}1\backslash /\mathrm{X}2=(\mathrm{S}12\backslash /\mathrm{S}13)/\backslash \{\mathrm{a}4\}\backslash /\mathrm{X}2\backslash /\mathrm{S}10$$(\mathrm{S}1\backslash /\mathrm{S}12\backslash /\mathrm{S}2)/\backslash \mathrm{X}1\backslash /\mathrm{X}2\backslash /\mathrm{S}6=(\mathrm{S}10\backslash /\mathrm{S}9)\backslash /(\mathrm{S}7/\backslash \mathrm{X}3)\backslash /\mathrm{S}2$,,$(\mathrm{S}5\backslash /\mathrm{S}3\backslash /\{\mathrm{a}4\})/\backslash (\mathrm{S}2\backslash /\mathrm{S}4\backslash /\mathrm{S}3\backslash /\mathrm{S}6)=(\mathrm{S}1\backslash /(\mathrm{X}1\backslash /\mathrm{X}2/\backslash (\mathrm{S}3\backslash /\mathrm{S}10)))/\backslash \mathrm{S}1\backslash /\mathrm{S}14$$]$.

[Xl, X2, X3], $[])$ .

contradiction deduced as follows$\{\mathrm{a}9\}\Leftrightarrow 0$

処理系は$\mathrm{B}$を $\{a1, a2, \ldots\}$ の有限部分集合と有限部分集合の補集合全体から成る 7–) 環としてにおける$\mathrm{B}(S1, s2, \ldots, X1, x2, x3)$$[\{\mathrm{a}1, \mathrm{a}9\backslash \}/\backslash (\mathrm{X}2\backslash /\sim_{\mathrm{X}1})+\{\mathrm{a}2.\mathrm{a}5,\mathrm{a}7\backslash \}/\backslash \mathrm{S}5$,,$\mathrm{S}1/\backslash (\mathrm{S}2/\backslash \sim\{\mathrm{a}5\backslash \}\backslash /(\mathrm{S}3/\backslash (\mathrm{S}4/\backslash \sim(\mathrm{X}1\backslash /\{\mathrm{a}6\backslash \}))))+(\mathrm{S}5/\backslash \mathrm{S}6)\backslash /(\mathrm{S}4/\backslash \mathrm{S}7/\backslash \mathrm{S}2)\backslash /\mathrm{S}8$$\mathrm{S}5/\backslash \mathrm{S}4/\backslash \mathrm{S}9/\backslash \mathrm{S}6/\backslash \mathrm{S}2/\backslash (\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}3\backslash /\{\mathrm{a}7\backslash \})/\backslash (\{\mathrm{a}9\backslash \}\backslash /\mathrm{X}2),$$\mathrm{S}2/\backslash (^{\sim}\{\mathrm{a}6.\mathrm{a}8\backslash \})+\mathrm{S}4\backslash /\mathrm{S}8,$$\mathrm{S}5/\backslash \mathrm{S}8/\backslash \sim(\mathrm{X}3\backslash /\{\mathrm{a}5, \mathrm{a}8\backslash \})$$\mathrm{S}2/\backslash (^{\sim}\{\mathrm{a}9\backslash \})+\mathrm{S}\mathrm{l}\mathrm{l}\backslash /\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}2\backslash /\{\mathrm{a}5, \mathrm{a}7\backslash \}\backslash /\mathrm{S}7.\mathrm{S}\mathrm{l}1/\backslash \mathrm{S}3$,,,$\mathrm{S}10/\backslash \mathrm{S}3,$ $\mathrm{S}12+\mathrm{s}9\backslash /\mathrm{S}7.\mathrm{S}9/\backslash \mathrm{S}7/\backslash \mathrm{S}15/\backslash \sim(\mathrm{X}1\backslash /\mathrm{X}2\backslash /\mathrm{X}3\backslash /\{\mathrm{a}4, \mathrm{a}5.\mathrm{a}6.\mathrm{a}7.\mathrm{a}8.\mathrm{a}9.\mathrm{a}\mathrm{l}0\backslash \})$$\{\mathrm{a}4\backslash \}/\backslash \mathrm{S}6+\{\mathrm{a}4\backslash \},\mathrm{x}1/\backslash \mathrm{S}9+\mathrm{X}1.\mathrm{X}3/\backslash \mathrm{S}7+\mathrm{X}3,$$\mathrm{S}1\backslash /\mathrm{S}10\backslash /\mathrm{X}1\backslash /\mathrm{X}2+(\mathrm{S}12\backslash /\mathrm{S}13)/\backslash \{\mathrm{a}4\backslash \}\backslash /\mathrm{X}2\backslash /\mathrm{S}10$$(\mathrm{S}1\backslash /\mathrm{S}12\backslash /\mathrm{S}2)/\backslash \mathrm{X}1\backslash /\mathrm{X}2\backslash /\mathrm{S}6+(\mathrm{S}10\backslash /\mathrm{S}9)\backslash /(\mathrm{S}7/\backslash \mathrm{X}3)\backslash /\mathrm{S}2$,,$(\mathrm{S}5\backslash /\mathrm{S}3\backslash /\{\mathrm{a}4\backslash \})/\backslash (\mathrm{S}2\backslash /\mathrm{S}4\backslash /\mathrm{S}3\backslash /\mathrm{S}6)+(\mathrm{S}1\backslash /(\mathrm{X}1\backslash /\mathrm{X}2/\backslash (\mathrm{S}3\backslash /\mathrm{S}10)))/\backslash \mathrm{S}1\backslash /\mathrm{S}14]$のブーリアングレブナー基底を [X 1, $X2,$ $X3$ ] $<[S1, S2, \ldots, S14]$ なるブロックオーダーで計算
し (解きたい変数が $X1,$ $X2,$ $X3$ なので) $X1,$ $X2,$ $X3$ のみを含む式を表示する. この実行例ではブーリアングレブナー基底に
$a9$

が他の

$a_{i}$$\mathrm{B}$の定数 $\{a9\}$ が含まれているので, 解が存在しない.

のどれかと等しければ解が存在する可能性があるので $a9$ を変数として実行してみる.

$?-\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}-\mathrm{s}\mathrm{e}\mathrm{t}-\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}$$([$$\{\mathrm{a}1, \mathrm{a}9\}/\backslash (\mathrm{X}2\backslash /\sim_{\mathrm{X}1})=\{\mathrm{a}2, \mathrm{a}5, \mathrm{a}7\}/\backslash \mathrm{S}5$,$\mathrm{S}1/\backslash (\mathrm{S}2/\backslash \sim\{\mathrm{a}5\}\backslash /(\mathrm{S}3/\backslash (\mathrm{S}4/\backslash \sim(\mathrm{X}1\backslash /\{\mathrm{a}6\}))))=(\mathrm{S}5/\backslash \mathrm{S}6)\backslash /(\mathrm{S}4/\backslash \mathrm{S}7/\backslash \mathrm{S}2)\backslash /\mathrm{S}8$.

$\mathrm{S}5/\backslash \mathrm{S}4/\backslash \mathrm{S}9/\backslash \mathrm{S}6/\backslash \mathrm{S}2/\backslash (\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}3\backslash /\{\mathrm{a}7\})/\backslash (\{\mathrm{a}9\}\backslash /\mathrm{X}2)=0.\mathrm{S}5/\backslash \mathrm{S}8/\backslash \sim(\mathrm{X}3\backslash /\{\mathrm{a}5.\mathrm{a}8\})=_{0}$$\mathrm{S}2/\backslash ("\{\mathrm{a}6.\mathrm{a}8\})=\mathrm{s}4\backslash /\mathrm{S}8,$$\mathrm{S}2/\backslash (^{\sim}\{\mathrm{a}9\})=\mathrm{S}\mathrm{l}\mathrm{l}\backslash /\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}2\backslash /\{\mathrm{a}5, \mathrm{a}7\}\backslash /\mathrm{S}7,$$\mathrm{S}\mathrm{l}1/\backslash \mathrm{S}3=0$

.

,

59

$\mathrm{s}\mathrm{l}0/\backslash \mathrm{s}3=0.\mathrm{S}\mathrm{l}2=\mathrm{s}9\backslash /\mathrm{s}7,$.

$\mathrm{S}9/\backslash \mathrm{s}7/\backslash \mathrm{S}\mathrm{l}5/\backslash \sim(\mathrm{X}\mathrm{l}\backslash /\mathrm{X}2\backslash /\mathrm{x}3\backslash /\{\mathrm{a}4, \mathrm{a}5.\mathrm{a}6.\mathrm{a}7, \mathrm{a}8.\mathrm{a}9.\mathrm{a}\mathrm{l}0\})=0$$\{\mathrm{a}4\}/\backslash \mathrm{S}6=\{\mathrm{a}4\},\mathrm{X}1/\backslash \mathrm{S}9=\mathrm{X}1,$$\mathrm{X}3/\backslash \mathrm{S}7=\mathrm{X}3,$$\mathrm{S}1\backslash /\mathrm{S}10\backslash /\mathrm{X}1\backslash /\mathrm{X}2=(\mathrm{S}12\backslash /\mathrm{S}13)/\backslash \{\mathrm{a}4\}\backslash /\mathrm{X}2\backslash /\mathrm{S}10$$(\mathrm{S}1\backslash /\mathrm{S}12\backslash /\mathrm{S}2)/\backslash \mathrm{X}1\backslash /\mathrm{X}2\backslash /\mathrm{S}6=(\mathrm{S}10\backslash /\mathrm{S}9)\backslash /(\mathrm{S}7/\backslash \mathrm{X}3)\backslash /\mathrm{S}2$.

,$(\mathrm{S}5\backslash /\mathrm{S}3\backslash /\{\mathrm{a}4\})/\backslash (\mathrm{S}2\backslash /\mathrm{S}4\backslash /\mathrm{S}3\backslash /\mathrm{S}6)=(\mathrm{S}1\backslash /(\mathrm{X}1\backslash /\mathrm{X}2/\backslash (\mathrm{S}3\backslash /\mathrm{S}10)))/\backslash \mathrm{S}1\backslash /\mathrm{S}14$$]$, [Xl , X2,X3], (A9)$)$.

constraint is satisfiable when$(^{\sim}\{\mathrm{a}2, \mathrm{a}4\})*\{\mathrm{a}9\}=0$

under the above condition [Xl,X2,$\mathrm{X}3$] has thefollowing form$(\{\mathrm{a}\mathrm{s}\}*\{\mathrm{a}9^{\}+}\{_{\mathrm{a}}5^{\}})*\mathrm{X}3*\mathrm{X}1=0$$(\{\mathrm{a}2,\mathrm{a}5,\mathrm{a}7\}*\{\mathrm{a}9\}+\{\mathrm{a}2, \mathrm{a}5.\mathrm{a}7\})*\mathrm{X}3*\mathrm{X}2=(\{\mathrm{a}2_{*}\mathrm{a}5,\mathrm{a}7^{\}*}\{\mathrm{a}9\}+\{\mathrm{a}2, \mathrm{a}5.\mathrm{a}7\})*\mathrm{X}3$$(\{\mathrm{a}2,\mathrm{a}4^{\}*}\{\mathrm{a}9^{\}})*\mathrm{X}3=0$$(\{\mathrm{a}1.\mathrm{a}2.\mathrm{a}4\}*\{\mathrm{a}9^{\}+\{\mathrm{a}}1\})*\mathrm{X}1=\{\mathrm{a}1,\mathrm{a}4\}*\{\mathrm{a}9^{\}+\{\}}\mathrm{a}1$$(\{\mathrm{a}1,\mathrm{a}2,\mathrm{a}4\}\mathrm{x}\{\mathrm{a}9^{\}+\{1\})2}\mathrm{a}*\mathrm{X}=0$

処理系はまず制約式の $\{a9\}$ を集合変数 $A9$ で置き換える. 次に$\mathrm{B}$を $\{a1, a2, a3, \ldots\}-\{a9\}$ の有限部分集合と有限部分集合の補集合全体から成る 7-j 環として $(\mathrm{B}(A9))(s1, s2, \ldots, x1, X2, X3)$

におけるブーリアングレブナー基底を [X 1, $X2,$ $X3$ ] $<[S1, S2, \ldots, s14]$ なるブロックオーダーで計算し定数部分 ($\mathrm{B}(A9)$の要素) の $A9$ を $\{a9\}$ で再び置き換えた式を表示してから $X1,$ $X2,$ $X3$ のみを含む式を表示する. この場合 $a9=a2$ あるいは $a9=a4$ のとき解が存在して下の式の $a9$ にそれぞれ $a2,$ $a4$ を代入したものが制約式の $a9$ にそれぞれ $a2$ , a4 を代入して得られた制約式の解 (ブーリアン・グレブナー基底の $X1,$ $X2,$ $X3$ のみを含む部分) になることが定理 5 よりいえる.
実際に制約式の $a9$ をそれぞれ $a2,a4$ で置き換えて実行してみると,$?-\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{V}\mathrm{e}_{-}\mathrm{s}\mathrm{e}\mathrm{t}-^{\mathrm{e}}1\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}$$([$$\{\mathrm{a}1, \mathrm{a}2\}/\backslash (\mathrm{X}2\backslash /\sim_{\mathrm{X}1})=\{\mathrm{a}2, \mathrm{a}5, \mathrm{a}7\}/\backslash \mathrm{S}5$,$\mathrm{S}1/\backslash (\mathrm{S}2/\backslash \sim\{\mathrm{a}5\}\backslash /(\mathrm{S}3/\backslash (\mathrm{S}4/\backslash \sim(\mathrm{X}1\backslash /\{\mathrm{a}6\}))))=(\mathrm{S}5/\backslash \mathrm{S}6)\backslash /(\mathrm{S}4/\backslash \mathrm{S}7/\backslash \mathrm{S}2)\backslash /\mathrm{S}8$.

$\mathrm{S}5/\backslash \mathrm{S}4/\backslash \mathrm{S}9/\backslash \mathrm{S}6/\backslash \mathrm{S}2/\backslash (\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}3\backslash /\{\mathrm{a}7\})/\backslash (\{\mathrm{a}2\}\backslash /\mathrm{X}2)=0,$ $\mathrm{S}5/\backslash \mathrm{S}8/\backslash$$\sim(\mathrm{X}3\backslash /\{\mathrm{a}5, \mathrm{a}8\})=0$$\mathrm{S}2/\backslash (^{\sim}\{\mathrm{a}6, \mathrm{a}8\})=\mathrm{s}4\backslash /\mathrm{S}8,$ $\mathrm{S}2/\backslash ("\{\mathrm{a}2\})=\mathrm{s}\mathrm{l}\mathrm{l}\backslash /\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}2\backslash /\{\mathrm{a}5, \mathrm{a}7\}\backslash /\mathrm{S}7,$ $\mathrm{S}\mathrm{l}1/\backslash \mathrm{S}3=0$$\mathrm{S}10/\backslash \mathrm{S}3=0$.S12$=\mathrm{S}9\backslash /\mathrm{S}7,$$\mathrm{X}3/\backslash \mathrm{S}7=\mathrm{X}3,$,,$(\mathrm{S}5\backslash /\mathrm{S}3\backslash /\{\mathrm{a}4\})/\backslash (\mathrm{S}2\backslash /\mathrm{S}4\backslash /\mathrm{S}3\backslash /\mathrm{S}6)=(\mathrm{S}1\backslash /(\mathrm{X}1\backslash /\mathrm{X}2/\backslash (\mathrm{S}3\backslash /\mathrm{S}10)))/\backslash \mathrm{S}1\backslash /\mathrm{S}14$$\{\mathrm{a}5\}*\mathrm{X}3*\mathrm{x}\mathrm{l}=0$$\{\mathrm{a}5, \mathrm{a}7\}*\mathrm{X}3*\mathrm{x}2=\{\mathrm{a}5.\mathrm{a}7\}*\mathrm{X}3$$\{\mathrm{a}2\}*_{\mathrm{X}3}=0$,$\mathrm{s}\mathrm{l}\backslash /\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}\mathrm{l}\backslash /\mathrm{X}2=(\mathrm{S}\mathrm{l}2\backslash /\mathrm{S}\mathrm{l}3)/\backslash \{\mathrm{a}4\}\backslash /\mathrm{X}2\backslash /\mathrm{S}\mathrm{l}0$$(\mathrm{S}1\backslash /\mathrm{S}12\backslash /\mathrm{S}2)/\backslash \mathrm{X}1\backslash /\mathrm{X}2\backslash /\mathrm{S}6=(\mathrm{S}10\backslash /\mathrm{S}9)\backslash /(\mathrm{S}7/\backslash \mathrm{X}3)\backslash /\mathrm{S}2$, [Xl, X2, X3] , $[])$ .

,,$\mathrm{S}9/\backslash \mathrm{S}7/\backslash \mathrm{S}15/\backslash \sim(\mathrm{X}1\backslash /\mathrm{X}2\backslash /\mathrm{X}3\backslash /\{\mathrm{a}4, \mathrm{a}5, \mathrm{a}6, \mathrm{a}7.\mathrm{a}8, \mathrm{a}2, \mathrm{a}10\})=0$$\{\mathrm{a}4\}/\backslash \mathrm{S}6=\{\mathrm{a}4\},$ $\mathrm{X}1/\backslash \mathrm{S}9=\mathrm{X}1,$

$]$

,

60

$\{\mathrm{a}1, \mathrm{a}2\}*\mathrm{X}1=\{\mathrm{a}1\}${al.

$\mathrm{a}2$}$*\mathrm{X}2\in 0$$?-\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}-^{8\mathrm{e}}\mathrm{t}-^{\mathrm{e}}1\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}$$([$$\{\mathrm{a}1, \mathrm{a}4\}/\backslash (\mathrm{X}2\backslash /\sim_{\mathrm{X}1})=\{\mathrm{a}2.\mathrm{a}5, \mathrm{a}\tau\}/\backslash \mathrm{S}5$.

$\mathrm{S}1/\backslash (\mathrm{S}2/\backslash \sim\{\mathrm{a}5\}\backslash /(\mathrm{S}3/\backslash (\mathrm{S}4/\backslash \sim(.\mathrm{X}1\backslash /\{\mathrm{a}6\}))))=(\mathrm{S}5/\backslash \mathrm{S}6)\backslash /(\mathrm{S}4/\backslash \mathrm{S}7/\backslash \mathrm{S}2)\backslash /\mathrm{S}8$,$\mathrm{S}5/\backslash \mathrm{S}4/\backslash \mathrm{S}9/\backslash \mathrm{S}6/\backslash \mathrm{S}2/\backslash (\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}3\backslash /\{\mathrm{a}7\})/\backslash (\{\mathrm{a}4\}\backslash /\mathrm{X}2)=0,$$\mathrm{s}5/\backslash \mathrm{S}8/\backslash \sim(\mathrm{X}3\backslash /\{\mathrm{a}5, \mathrm{a}8\})=0$$\mathrm{S}2/\backslash (^{-}\{\mathrm{a}6, \mathrm{a}8\})=\mathrm{S}4\backslash /\mathrm{S}8,$$\mathrm{S}10/\backslash \mathrm{S}3=0$, S12$=\mathrm{S}9\backslash /\mathrm{S}7,$$\{\mathrm{a}4\}/\backslash \mathrm{S}6=\{\mathrm{a}4\},$$\mathrm{S}2/\backslash (^{\sim}\{\mathrm{a}4\})=\mathrm{S}\mathrm{l}\mathrm{l}\backslash /\mathrm{S}\mathrm{l}0\backslash /\mathrm{X}2\backslash /\{\mathrm{a}5, \mathrm{a}7\}\backslash /\mathrm{S}7,$$\mathrm{S}\mathrm{l}1/\backslash \mathrm{S}3=0$.

$\mathrm{S}9/\backslash \mathrm{S}7/\backslash \mathrm{S}15/\backslash \sim(\mathrm{X}1\backslash /\mathrm{X}2\backslash /\mathrm{X}3\backslash /\{\mathrm{a}4, \mathrm{a}5, \mathrm{a}6, \mathrm{a}7, \mathrm{a}8, \mathrm{a}4, \mathrm{a}\mathrm{l}\mathrm{o}\})=0$$\mathrm{x}1/\backslash \mathrm{S}9=\mathrm{X}1,$$\mathrm{X}3/\backslash \mathrm{S}7=\mathrm{X}3,$,,$\mathrm{S}1\backslash /\mathrm{S}10\backslash /\mathrm{X}1\backslash /\mathrm{X}2=(\mathrm{S}12\backslash /\mathrm{S}13)/\backslash \{\mathrm{a}4\}\backslash /\mathrm{X}2\backslash /\mathrm{S}10_{*}$.

$(\mathrm{S}1\backslash /\mathrm{S}12\backslash /\mathrm{S}2)/\backslash \mathrm{X}1\backslash /\mathrm{X}2\backslash /\mathrm{S}6=(\mathrm{S}10\backslash /\mathrm{S}9)\backslash /(\mathrm{S}7/\backslash \mathrm{X}3)\backslash /\mathrm{S}2$$(\mathrm{S}5\backslash /\mathrm{S}3\backslash /\{\mathrm{a}4\})/\backslash (\mathrm{S}2\backslash /\mathrm{S}4\backslash /\mathrm{S}3\backslash /\mathrm{S}6)=(\mathrm{S}1\backslash /(\mathrm{X}1\backslash /\mathrm{X}2/\backslash (\mathrm{S}3\backslash /\mathrm{S}10)))/\backslash \mathrm{S}1\backslash /\mathrm{S}14$$]$, [Xl , X2, X3], $[])$ .

$\{\mathrm{a}5\}*\mathrm{X}3*\mathrm{x}\mathrm{l}=0$$\{\mathrm{a}2, \mathrm{a}5, \mathrm{a}7\}*_{\mathrm{X}}3*\mathrm{x}2=\{\mathrm{a}2, \mathrm{a}5, \mathrm{a}7\}*\mathrm{x}3$$\{\mathrm{a}4\}*\mathrm{X}3=0$$\{\mathrm{a}1, \mathrm{a}4\}*\mathrm{X}1=\{\mathrm{a}1, \mathrm{a}4\}$$\{\mathrm{a}1, \mathrm{a}4\}*\mathrm{X}2=0$

6.6 おわりに係数環が$*\backslash$

一ター環でいくつかの計算可能性に関する条件を満たすとき syzygy 基底の計算によって弱グブナー基底といわれるものが計算可能であることが知られている$([\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{k}_{\mathrm{S}}78],[\mathrm{Z}\mathrm{a}\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{S}78])$.

ここで述べたブーリアングブナー基底はこの弱グブナー基底にほかならないが, 重要な点はそれが単項リダクションのみによって定義でき計算できる点である. これにより上の方法では実際に計算するのがほとんど不可能であったのが容易に計算できるようになった. また定理 3 と定理 4 によるアルゴ

リズムの改良は非常に有効である. 前節であげた最初の例では実際に計算されたあるのに対し計算しないですんだ冗長な

universal グブナー基底$\mathrm{S}$$\mathrm{S}$多項式は 4648 個で多項式は 8621 個あった.

$([\mathrm{W}\mathrm{e}\mathrm{i}\mathrm{S}\mathrm{p}\mathrm{f}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}871)$, すなわちすべてのアドミシブ) 全)|| 序においてグブ

ナー基底となるような基底も剰余環におけるブーリアングブナー基底においては著しく容易に構成できる. 剰余環においてはすべての変数の次数が高々 1 なので項の数は有限個しか存在しないからで
ある.

61

参考文献
[Aiba $88$ ]$\mathrm{A}\mathrm{k}\mathrm{i}\mathrm{r}\mathrm{a}$Aiba, Ko Sakai, Yosuke Sato, David J.Hawley, Ryuzo Hasegawa (1988). Constraint

Logic Programming Language CAL Proceedings of The International Conference on Fifth

Generation Computer, 263-276[Buchberger $65$ ], B. (1965). Ein Algorithmus zum Auffinden der Basiselemente des$\mathrm{B}\mathrm{u}\mathrm{C}\mathrm{h}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{r}$Restklassenrings nach einem nulldimensionalen Polynomideal.

$\mathrm{P}\mathrm{h}\mathrm{D}$thesis, Universit\"at Inns-

bruck.
[Buchberger $85$ ], B. (1985). Gr\"obner bases:$\mathrm{B}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{r}$An algorithmic method in polynomial

ideal theory, chap 6 in Recent Trends in Multidimentional System Theory, N. K. Bose Ed.,
Reidel Publ. Comp.
[Rudeanu $74$ ][Sakai $88$ ], S. (1974). Boolean Functions and Equations, North-Holland$\mathrm{R}\mathrm{u}\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{n}\mathrm{u}$$\mathrm{s}\mathrm{a}\mathrm{k}\mathrm{a}\mathrm{i}$, K., Sato, Y. (1988). Boolean Gr\"obner bases. Proceeding of LA-Symposium in

winter, RIMS, Kyoto Univ., 29-40[Sakai $90$ ]$\mathrm{S}\mathrm{a}\mathrm{k}\mathrm{a}\mathrm{i}$, K., Sato, Y., Menju, S. (1990). Boolean Gr\"obner bases(revised). ICOT Technical

Report 613, also submitted for publication.
[Trinks$781^{\mathrm{T}\mathrm{r}}\mathrm{i}\mathrm{n}\mathrm{k}\mathrm{S}$, W. (1978). \"Uber B.Buchbergers Verfahren, Systeme algebraischer Gleichungenzu l\"osen. J.Number Theory 10,[Weispfenning $87$ ]$\mathrm{W}\mathrm{e}\mathrm{i}_{\mathrm{S}}\mathrm{p}\mathrm{f}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$$475\triangleleft 88$.

, V. (1987). Constructing universal Gr\"obner bases, Springer LNCS

356, 408-417.
[Weispfenning $89$ ]$\mathrm{W}\mathrm{e}\mathrm{i}_{\mathrm{S}}\mathrm{P}\mathrm{f}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$, V. (1989). Gr\"obner bases in polynomial rings over commutative

regular rings, EUROCAL ’87,
[Weispfenning 92|$\mathrm{J}.\mathrm{H}$. Davenport Ed., Springer LNCS$\mathrm{V}\mathrm{o}\mathrm{l}378$, 336-347.

, V. (1992). Comprehensive Gr\"obner bases, J.Symb. Comp. 14/1,1-$\mathrm{w}_{\mathrm{e}}\mathrm{i}\mathrm{s}_{\mathrm{P}^{\mathrm{f}}}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$29.
[Zacharias $78$ ]Thesis at$\mathrm{Z}\mathrm{a}\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{s}$$\mathrm{M}.\mathrm{I}$, G. (1978). Generalized Gr\"obner bases in commutative polynomial rings.

T., Dept. Comp. Sci.

[Sato 93] 佐藤洋祐, 毛受哲, 相場亮 (1993). ブーリアングレブナー基底の Syzygy 基底による特徴付
け. 情報処理学会論文誌 Vol. 34 No 71549-1554