The technique used by Bernhard Pfahringer was exactly the right one for
Competitions 1 and 3.  His program used a search he describes as essentially
brute-force, but with some necessary sophistication.  The rest of this file
has the remainder of his description (with an added reference and
acknowledgement).

                               ...               In principle I did just
generate all possible clauses of size 3,4,... and so on in a depth-first
iterative deepening manner [2]. Every completed clause was checked for 
completeness and coverage. The final version of the program solved Competition
1 and 3 simultanously (generation of clauses did not depend on the
examples) using about one day realtime on Sparc 10.

History: Originally I started with a version of Foil [3] that I've
implemented in Prolog some time ago. After realizing that an optimal
solution was required, I did a few experiments which proved depth-first
iterative deepening to be feasible.  So I just kept the
literal-generator of my original Foil clone. This generator is efficient,
because it uses types for variables, ensures that only one 'canonical' form
of a literal is generated if there are a few symmetric ones possibly, and
it makes a distinction between literals that introduce new variables
(generators) and literals that don't (tests).

At some point I made the decision that introducing 'sub-predicates' is
probably too costly. So I concentrated on the expressiveness of the 
generated prolog clauses. Incrementally I first added 'or', then 'findall'
and then tried to add recursion. At that point I was still using the
examples for checking while generating - immediately dropping clauses
that would not cover all positive examples. But then I really could not
figure it out for the interaction of or and recursion. That was when
I finally dropped using the examples for pruning and started to just
generate all syntactically possible clauses. 

The first attempts were too inefficent - way too many duplicate clauses
were generated. But then I realized that because I would generate all
clauses, I could impose some ordering without losing completeness. So
for every 'and-branch' (the toplevel originally is an and-branch, every
or introduces two independent and-branches, findall yields another one)
first all possible generators are produced, then with a now fixed set
of variables all possible tests are tried (of course always staying
within the given size-bounds). Introduction of 'or' is only allowed
at the last position in an 'and-branch'.

Testing of the clauses needed indirection through a check against
run-away recursion: the worst case was the a combination of findall
and recursion were the list grew quadratically at every recursive call
quickly overflowing the prolog-stack.

After trying to add cut and negation, I found so many possible sources of
incompleteness that I just dropped all smarts. I just defined and
implemented a simple grammar to produce valid clauses:
 s -> any_literal
 s -> s,s
 s -> ( s ; s)
 s -> \+ s
 s -> ( s, ! ; s)
 s -> ( s, !, s ; s)
 s -> findall(1,s,[1])    ;; test iff exactly one occurence
 ...
 s -> findall(1,s,[1,1,1,1])
 s -> findall(Var,s,TrainVar)
Sizes are checked immediately to enable early pruning, e.g. for
's -> \+ s' the allocated size must be > 2 because '\+' costs one and
the subsequent 's' will cost at least two. Every call must produce
exactly the size called for. For symmetric productions (e.g. s -> s,s)
always the first subpart will be greater or equal in size to the second
subpart.

This purely size-oriented approximation to a normalform yielded sufficient
efficiency.

Final re-expression: I dropped the run-away recursion checks, substituted
'or' for '\+' (I am using Sicstus [1]), and reordered literals were ordering
seemed 'unnatural' to me, like if an 'or' contained a branch with recursive
call and one without, I prefer have the recursive call in the second
branch, just like recursive predicate definitions where you first state
the base case and then the recursion case. 



I am indepted to the Austrian Research Institute for Artificial Intelligence
for providing the necessary computing resources.



Reference

[1] Carlsson M., Widen J.: Sicstus Prolog Users Manual, Swedish Institute of
    Computer Science, SICS/R-88/88007C, 1990.

[2] Korf R.E.: Depth-First Iterative-Deeping: An Optimal Admissible Tree Search,
    Artificial Intelligence, 27(1), 97-110, 1985.

[3] Quinlan J.R., Cameron-Jones R.M.: FOIL: A Midterm Report, in Brazdil
    P.B.(ed.), Machine Learning: ECML-93, Springer, Berlin, pp.3-20, 1993.