1) Reducible
可归约
2) reducibility
可归约性
1.
A practical necessary and sufficient condition is obtained for the reducibility decision of flow graph G, and a relevant algorithm which finds the dominators in G at the sam time is given.
本文得到了流图Ｇ可归约性判定的一个实用的充要条件。
3) ground reducibility
基可归约性
4) irreducible rule set
不可归约规则集
1.
Several works suggest proving termination by using triggering and activation graphs at compile-time, and computing an irreducible rule set is the key technique.
主动数据库中规则集的可终止性判定是一个重要问题,已经成为一个研究热点·有些研究工作提出了在编译阶段运用触发图和活化图的方法解决这个问题,其中的一个关键技术就是计算主动规则集的不可归约规则集·现有的计算方法由于具有一定保守性,使得计算出的不可归约规则集仍可进一步地归约,这无疑将影响到规则集的可终止性判定的准确性和运行阶段规则分析的效率·经过深入分析活化规则可无限执行的特点,提出了活化路径等概念·基于这些概念,提出了一个计算主动规则集的不可归约规则集的有效算法,使现有方法求得的不可归约规则集得到进一步的归约
5) Turing reducibility
图灵可归约性
6) FOL-reducibility
一阶逻辑可归约性
补充资料：多项式空间归约
多项式空间归约
polynomial space reduction
duoxiangshi kongiian guiyue多项式空间归约(po.”0而目spacereduc·tion)一种特殊的、归约函数是多项式空间可计算的复杂性归约。 设Ll，LZ是万上的两个语言，若存在函数S:N~N，及S空间可计算函数f:艺肠~刃并，使得 (l)对任何x任乞’，xeLI当且仅当f(x)eLZ; (2)存在正整数C，使对任何xe艺.有s(}f(x)})(岱(}x})，则称Ll可S空间归约到LZ，记为Ll戳LZ。特别当限制s为多项式函数时，则称Ll可多项式空间归约到LZ。空间归约中较为重要的一种是限制S为对数函数吨，称之为对数空间归约，可对复杂性类进行更“细”的划分，特别是研究尸和N吨等复杂性类，其时间资源不超过确定的多项式时间时，多项式时间归约则无法对其进行分类。
说明：补充资料仅用于学习参考，请勿用于其它任何用途。