有界重なり項書換え系と構成的正則保存性

北岡 康司 (9751040)


項書換え系においては, 会同関係や局所合流性などの重要な性質があるが, これらの性質は一般には決定不能である. 会同関係や局所合流性などの問題が 決定可能である部分クラスとして構成的正則保存書換え系が知られている. しかし, 与えられた書換え系が構成的正則保存であるかどうかは決定不能である. これまで, ある書換え系が構成的正則保存であるための決定可能な十分条件について, いくつかの研究成果が報告されている. 本論文では構成的正則保存項書換え系の決定可能な部分クラスとして, 有界重なり書換え系を導入した. この有界重なり書換え系は, 書換え規則の突出関係から導かれるグラフによって定義される決定可能なクラスであり, これまで知られていた決定可能な構成的正則保存書換え系である 右線形単項的書換え系および線形一般化準単項的書換え系のクラスを真に含む. 本論文では, この有界重なり書換え系が 構成的正則保存書換え系の決定可能な部分クラスであること, および, これまで知られていた決定可能な構成的正則保存書換え系の部分クラスを真に含むことを示した.