Inductive Logic Programming considers almost exclusively universally quantied theories. To add expressiveness, prenex conjunctive normal forms (PCNF) with existential variables should also be considered. ILP mostly uses learning with refinement operators. To extend refinement operators to PCNF, we should first do so with substitutions. However, applying a classic substitution to a PCNF with existential variables, one often obtains a generalization rather than a specialization. In this article we define substitutions that specialize a given PCNF and a weakly complete downward refinement operator. Moreover, we analyze the complexities of this operator in different types of languages and search spaces. In this way we lay a foundation for learning systems on PCNF. Based on this operator, we have implemented a simple learning system PCL on some type of PCNF.

PCNF, completeness, learning, refinement, substitutions
Optimization Techniques; Programming Models; Dynamic Analysis (jel C61), Business Administration and Business Economics; Marketing; Accounting (jel M), Production Management (jel M11), Transportation Systems (jel R4)
Erasmus Research Institute of Management
ERIM Report Series Research in Management
Copyright 2000, S-H. Nienhuys-Cheng, W. Van Laer, J. Ramon, L. De Raedt, This report in the ERIM Report Series Research in Management is intended as a means to communicate the results of recent research to academic colleagues and other interested parties. All reports are considered as preliminary and subject to possibly major revisions. This applies equally to opinions expressed, theories developed, and data used. Therefore, comments and suggestions are welcome and should be directed to the authors.
Erasmus Research Institute of Management

Nienhuys-Cheng, S-H, van Laer, W, Ramon, J, & de Raedt, L. (2000). Generalizing Refinement Operators to Learn Prenex Conjunctive Normal Forms (No. ERS-2000-39-LIS). ERIM Report Series Research in Management. Erasmus Research Institute of Management. Retrieved from