权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

項書換え系の単一化手法に関する研究

术语重写系统统一方法研究

基本信息

批准号：
07780267
负责人：
楫勇一
金额：
$ 0.58万
依托单位：
Nara Institute of Science and Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07780267/
关键词：
単一化問題代入制約項書換え系計算複雑さ

项目摘要

代入制約付き単一化問題(CS-UP)の判定手続きを拡張・一般化することを目的として研究を行ってきたが、手続きの対象となるクラスをわずかに広げただけでも同問題が決定不能となる場合が多く、CS-UPの計算複雑さが予想以上に大きいことが明らかになった。そこで問題の対象をCS-UPにおいて公理系が存在しない場合(代入制約付き構文的単一化問題、CS-SUP)に限定し、CS-SUPの計算量が入力クラスの大きさに対しどのように変化するかを考察した。具体的には、利用可能な項が(1)閉じている、(2)閉じているか線形である、(3)一般に非線形でも良い;ゴール項が(A)ともに線形である、(B)非線形でも良い;ゴール項に共通変数が(a)存在する、(b)存在しない;の3種の条件を考え、計12の入力クラスに対するCS-SUPの決定可能性、計算量について考察を行った。その結果、クラス3Aa(上記条件3、A、aの全てを満足する入力クラス)、3Ab、3Ba、3Bbに対するCS-SUPは決定不能であること、クラス1Aa、1Ab、1Ba、1Bb、2Aa、2Ab、2Ba、2Bbに対するCS-SUPは決定可能であることが明らかになった。またCS-SUPの計算量について、クラス2Ab、2Ba、2Bbに対してはNP-困難であること、クラス1Aa、1Ba、1Bbに対してはNP-完全であること、さらにクラス2Aa、1Aaに対しては決定性多項式時間で解けることを示した。これらの結果は理論的に興味深いだけでなく、CS-UPの判定手続きを拡張する上においても大きな示唆を与えるものであると考えられる。

Substitution of the problem to determine the hand of the problem (CS-UP), the purpose of the study, the hand of the problem to determine the situation, the CS-UP calculation of the problem to determine the situation. CS-UP axiom system exists for the object of the problem (simplification problem of substitution constraint structure, CS-UP). Specifically, the use of possible terms: (1) closed;(2) closed;(3) generally non-linear;(A) non-linear;(B) non-linear;(a) existence;(b) existence;(c) three conditions for the CS-sup decision;(d) calculation of 12 input forces. As a result, CS-sup decision 3Aa(entry force for all conditions 3, A, and a above), 3Ab, 3Ba, and 3Bb cannot be determined, CS-sup decision 1Aa, 1Ab, 1Ba, 1Bb, 2Aa, 2Ab, 2Ba, and 2Bb cannot be determined, and CS-sup decision 1Aa, 1Ab, 1Ba, 1Bb, 2Aa, 2Ab, 2Ba, and 2Bb cannot be determined. CS-sup calculation quantity is NP-hard, 1Aa, 1Ba, 1Bb is NP-complete, 2Aa, 1Aa is deterministic polynomial time. The result is that the theory is very interesting, and the CS-UP decision is very important.