TY - JOUR
T1 - Inferring minimal functional dependencies in Horn and q-Horn theories
AU - Ibaraki, Toshihide
AU - Kogan, Alexander
AU - Makino, Kazuhisa
N1 - Funding Information:
The authors acknowledge the partial support by the Office of Naval Research (grant N00014-92-J1375) and a Scientific Grant-in-Aid from the Ministry of Education, Culture, Sports, Science and Technology of Japan. A part of this work was done during the second author’s visit at Kyoto University, which was supported by a Scientific Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors express their sincere gratitude to the anonymous referees whose comments helped in improving this paper.
PY - 2003/8
Y1 - 2003/8
N2 - In this paper, we study various problems related to the inference of minimal functional dependencies in Horn and q-Horn theories. We show that if a Horn theory is represented by a Horn CNF, then there exists an incrementally polynomial algorithm for inferring all minimal functional dependencies. On the other hand, if a Horn theory is represented as the Horn envelope of a given set of models, then there exists a polynomial total time algorithm for this inference problem if and only if there exists such an algorithm for dualizing a positive CNF. Finally, we generalize our results to the case of q-Horn theories, and show that all the considered problems can be reduced in polynomial time to the corresponding problems for Horn theories.
AB - In this paper, we study various problems related to the inference of minimal functional dependencies in Horn and q-Horn theories. We show that if a Horn theory is represented by a Horn CNF, then there exists an incrementally polynomial algorithm for inferring all minimal functional dependencies. On the other hand, if a Horn theory is represented as the Horn envelope of a given set of models, then there exists a polynomial total time algorithm for this inference problem if and only if there exists such an algorithm for dualizing a positive CNF. Finally, we generalize our results to the case of q-Horn theories, and show that all the considered problems can be reduced in polynomial time to the corresponding problems for Horn theories.
UR - http://www.scopus.com/inward/record.url?scp=0037262289&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037262289&partnerID=8YFLogxK
U2 - 10.1023/A:1023098325064
DO - 10.1023/A:1023098325064
M3 - Article
AN - SCOPUS:0037262289
SN - 1012-2443
VL - 38
SP - 233
EP - 255
JO - Annals of Mathematics and Artificial Intelligence
JF - Annals of Mathematics and Artificial Intelligence
IS - 4
ER -