逻辑程序的实现策略(二)

六、算法的时间复杂性 算法1是严格按Horn子句和上下文无关文法的对应关系用Earley思想设计的。一般来说,Horn子句对应了上下文无关文法的所有可能性,它可能对应无穹界多义文法,有界多义文法,两义文法,非两义文法及在限状态上下文无关文法。正因为Earley算法是极为通用的上下文无关文法,它对任一种上下文无关文法都可求解。所以算法1的功能对所有Horn子句系统亦是通用的,只不过是对不同类型的Horn子句系统,对不同的问题,其算法复杂性是不同的。