Learning from examples in First Order Logic, also known as Inductive Logic Programming (ILP), constitutes a central topic in Machine Learning, with relevant applications to problems in complex domains, e.g., natural language and computational biology. Learning can be viewed as a search problem in the space of all possible hypotheses. Given a background knowledge, a set of positive examples and a set of negative examples, expressed in First Order Logic, one has to find a hypothesis which covers all positive examples and none of the negative ones. This problem is NP-hard even if the...