有界経路重なり項書換え系の停止性問題について
阿部 武徳 (9951001)
停止性が決定可能となる項書換え系の部分クラス，
準直交線形逆有界経路重なり項書換え系を提案する．
右線形有界経路重なり項書換え系は，
項の集合の正則性を利用して定義される
構成的正則保存項書換え系の決定可能な部分クラスとして
提案されていた．また，項の集合の正則性を利用して，
準直交成長的項書換え系の停止性が決定可能になることが示されていた．
そこで，本論文では準直交線形逆有界経路重なり項書換え系を提案し，
そのクラスに含まれる
項書換え系の停止性問題が決定可能となることを示す．
このクラスは，逆右線形有界経路重なり項書換え系の部分クラスであり，
準直交成長的項書換え系には含まれない項書換え系を含むクラスである．
特に，このクラスは，線形な準直交成長的項書換え系のクラスを真に含む．