Induction of Prolog programs with Markus

This paper describes empirical Inductive Logic Programming system Markus, which was designed as a shell for experimenting in different real-life domains. The current version of the system uses as its basis ’covering’ paradigm (also used by some other systems, e.g. Quinlan’s Foil). Within this paradigm, the development of single program clauses is performed by iterative deepening search of optimally generated refinement graphs (also used in Shapiro’s Model Inference System). The system was successfully applied to several nontrivial learning tasks: construction of qualitative models, program verification, formula invention and construction of some typical Prolog programs, the most difficult being the quick-sort.