On the complexity of equivalence between recursive and nonrecursive Datalog programs
Surajit Chaudhuri, Moshe Y. Vardi · 1994
In a previous paper, we have proved tight complexity bounds for the equivalence of recursive and nonrecursive Datalog programs: triply exponential time in general and doubly-exponential space for linear programs. In this paper, we show that under realistic restrictions on the classes programs under consideration, equivalence of recursive and nonrecursive programs can be less intractable; for the classes of programs we consider the complexity of equivalence ranges from NP to co-NEXPTIME.