Manuel Blum, Ashok K. Chandra, et al.
Information Processing Letters
It is shown that the general inference problem for embedded implicational dependencies (EIDs) is undecidable. For the more important case of finite inference (i.e., inference for finite data bases), the problem is not even recursively enumerable (r.e.); rather, it is complete in co-r.e. These results hold even for typed EIDs without equality, as well as for (untyped) template dependencies. The case for typed template dependencies remains open. The complexity of the inference problem for full dependencies has also been characterized - it is complete in exponential time for full implicational dependencies, and even for full typed template dependencies.
Manuel Blum, Ashok K. Chandra, et al.
Information Processing Letters
Ashok K. Chandra, Steven Fortune, et al.
Journal of Computer and System Sciences
Alok Aggarwal, Ashok K. Chandra, et al.
SPAA 1989
Ashok K. Chandra, George Markowsky
Discrete Mathematics