Code:Prolog (SICStus, Quintus and Arity)
References:Grobelnik 1992

MARKUS, a derivative of Shapiro's Model Inference System MIS, induces Prolog programs from positive and negative examples. MARKUS employs a covering strategy as, e.g., FOIL. It induces clauses with functions and is able to start induction with a preliminary incomplete or inconsistent definition of the target predicate which is then refined.

For inducing single clauses, MARKUS searches a refinement graph. The search starts with the most general clause which is specialised by applying the refinement operators taken over from MIS. In contrast to MIS, MARKUS generates an optimal refinement graph, i.e., a refinement graph without duplicate nodes, thus improving efficiency. The refinement graph is searched by iterative deepening search. When MARKUS encounters a clause covering at least one yet uncovered positive and no negative example, the clause is added to the predicate definition. Redundant clauses are removed from the predicate definition.

As MARKUS realizes an exhaustive search, restricting the hypothesis space is crucial for learning. Therefore, MARKUS offers elaborate mechanisms for explicit and implicit declaration of the language bias. First of all, the language bias which is defined implicitly by the refinement operator can be adjusted to the learning task by choosing the appropriate refinement operator, as MARKUS offers a refinement operator for learning DCG clauses and a general refinement operator for inducing logic programs. The application of the general refinement operator is guided by input/output mode declarations and type definitions for the arguments of the target and background predicates specified by the user. A set of parameters determines the form of clauses generated by the refinement operator. E.g., these parameters allow to define the maximum number of body literals, and the maximum structure depth of head arguments. For further tuning of the search space, the user can specify various concrete syntactic restrictions within individual type and background predicate definitions in a uniform manner. E.g., these restrictions make it possible to define argument symmetry or to prevent particular combinations of literals. MARKUS is a non-interactive learner, learning from positive and negative examples which offers various options for adjusting the system bias. It uses logic with functors and is able to generate hypothesis clauses with negated body literals. The background knowledge is defined intensionally. The user has to provide mode declarations and type definitions for the arguments of target and background predicates.


  1. M. Grobelnik. MARKUS: An optimized model inference system. In C. Rouveirol, editor, Proceedings of the ECAI-92 Workshop on Logical Approaches to Machine Learning, 1992.
  2. M. Grobelnik. Induction of Prolog programs with MARKUS. In Y. Deville, editor, Proceedings of the 3rd International Workshop on Logic Program Synthesis and Transformation. Workshops in Computing, Springer-Verlag, 1993.
  3. E.Y. Shapiro. Algorithmic Program Debugging. The MIT Press, 1983.

back to index