Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1981 | 10.1145/800076.802488 | STOC '81 Proceedings of the thirteenth annual ACM symposium on Theory of computing |
Keywords | Field | DocType |
template dependency,important case,exponential time,full implicational dependency,inference problem,embedded implicational dependency,general inference problem,finite inference,finite data base,full dependency,petri net,decidability | Discrete mathematics,Petri net,Exponential function,Computer science,Inference,Recursively enumerable language,Algorithm,Theoretical computer science,Decidability,Reachability problem,Dependency theory (database theory),Undecidable problem | Conference |
Citations | PageRank | References |
49 | 16.23 | 29 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashok K. Chandra | 1 | 3116 | 1215.02 |
| Harry R. Lewis | 2 | 532 | 145.43 |
| Johann A. Makowsky | 3 | 509 | 130.82 |