=================================================================
LGEN - Lambda GENeralization
Learning clauses from positive-only examples
by searching a lambda-generalization graph
=================================================================
This directory contains the LGEN system and a number of examples
illustrating its work. The system is supplied in Prolog source
code with the file "lgen.pl". The present version of LGEN runs
on SICStus Prolog v.3. All the other files contain example data
sets for learning various predicate definitions.


Description of LGEN

=================================================================
References:
=================================================================
Markov, Z. Lambda-Subsumption and Its Application to Learning
    from Positive-only Examples, in: S. Muggleton (ed.),
    Proceedings of ILP-96, Stockholm, August, 1996,
    Selected Papers, Lecture Notes in Artificial Intelligence,
    Vol.1314, Springer, 1997, 377-396.

Markov, Z. Generalization under Implication by lambda-Subsumption,
    in: David Page (ed.), Proceedings of ILP-98, Madison,
    Wisconsin, USA, July 22-24, 1998, Lecture Notes in Computer
    Science, Vol. 1446, Springer, 1998, 215-224.

=================================================================
Top level predicate: lgen(+TargetPredicate/Arity,+SearchMode)
=================================================================
    TargetPredicate/Arity - specifies the target predicate to
      be induced. The clauses for the target predicate are
      printed and then asserted in the database as facts:
      lgen_clause(Example,Clause,Cover), where
        Example - the example from which Clause is induced;
        Clause  - the induced clause;
        Cover   - list of examples covered by Clause.
    SearchMode is a parameter specifying the search algorithm:
      df - depth-first search;
      DepthBound  - integer number (>0) specifying the maximal
           depth for iterative deepening search.

=================================================================
Data required (must be asserted in the database):
=================================================================
  1. background([P1/A1,...,Pn/An]).
     Bi - predicate name, Ai - arity
  2. Clauses for P1,...,Pn and instances of TargetPredicate.

=================================================================
Requirements to the data:
=================================================================
  1. All data are specified in DATALOG, i.e. all predicate 
     agruments must be of type atomic (atoms or numbers).
  2. Do not use built-in predicate names (e.g. append,
     member etc.) to avoid name clashes.
  3. Since there are no argument types, preferably use
     different domains for different types of arguments.
=================================================================
Requirements to the Prolog system: SICStus Prolog v.3
=================================================================
  If another version of Prolog is used then it must provide:
   1. Standard Edinburgh syntax
   2. Built-in definitions of:
     * findall(Term,Goal,List) - List contains all possible
         instantiations of Term, when executing Goal;
     * \+(Goal) - negation by failure.

=================================================================
How to run LGEN
=================================================================
1. Consult (or compile) the source file "lgen.pl".

2. Consult (or compile) the data set file (e.g. "member1.pl").

3. Type "lgen(TragetPredicate/Arity,SearchMode)." at the top level
   (e.g. lgen(memb/2,2) ).

=================================================================
Example session
=================================================================

?- ['c:/lgen/lgen'].
{consulting c:/lgen/lgen.pl...}
{c:/lgen/lgen.pl consulted, 170 msec 43680 bytes}

yes
?- ['/lgen/member1'].
{consulting c:/lgen/member1.pl...}
{c:/lgen/member1.pl consulted, 20 msec 1368 bytes}

yes
?- lgen(memb/2,3). % using iterative deepening with depth bound 3
Searching clause for memb(b,[a,b,c])...
Depth 0 ...
Depth 1 ...
Depth 2 ...
Found memb(A,B):-components(B,C,D),memb(A,D)
Searching clause for memb(b,[b,c])...
Depth 0 ...
Depth 1 ...
Depth 2 ...
Found memb(A,B):-components(C,D,E),components(B,A,C)
Searching clause for memb(c,[c])...
Depth 0 ...
Depth 1 ...
Found memb(A,B):-components(B,A,C)
Check for clause subsumption...
Removing memb(A,B):-components(C,D,E),components(B,A,C)

Clauses found in 0.46s
-----------------------
memb(A,B):-components(B,C,D),memb(A,D)
memb(A,B):-components(B,A,C)

?- lgen(memb/2,df).   % using depth-first search
Searching clause for memb(b,[a,b,c])...
Found memb(A,B):-components(B,C,D),memb(A,D)
Searching clause for memb(b,[b,c])...
Found memb(A,B):-components(C,D,E),components(B,A,C)
Searching clause for memb(c,[c])...
Found memb(A,B):-components(B,A,C)
Check for clause subsumption...
Removing memb(A,B):-components(C,D,E),components(B,A,C)

Clauses found in 0.33s
-----------------------
memb(A,B):-components(B,C,D),memb(A,D)
memb(A,B):-components(B,A,C)


=================================================================
FOR MORE INFORMATION CONTACT:

Zdravko Markov, Ph.D.
Associate Professor of Computer Science, 
Central Connecticut State University
1615 Stanley Street, New Britain, CT 06050, U.S.A.
Phone:  (860) 832-2711
Fax:    (860) 832-2712
E-mail: markovz@ccsu.edu
URL: http://www.cs.ccsu.edu/~markov/
=================================================================