語問題を基底等式集合の語問題に帰着可能な等式集合のクラスについて

摘要

等式集合の語問題は，2つの項を与えたときに，等式集合のもとで2つの項が等しいかどうかを決定する問題である．本論文では線形，シャロー，変数非消去かつ非崩壊な規則からなる等式集合の語問題が，等式集合と2つの項から定められる基底項を各等式に代入する変換を用いることにより，変数を持たない等式集合の語問題へ帰着可能であることを示す．この結果より，変数を持たない等式集合の語問題判定アルゴリズムを用いて，目的の語問題を解くことが可能となる．