More compact definition

Question

Given word/1,

word(W) :-
   abs(ABs),
   ABs = W.

abs([]).
abs([AB|ABs]) :-
   abs(ABs),
   ab(AB).

ab(a).
ab(b).

?- word(W).
   W = []
;  W = [a]
;  W = [b]
;  W = [a,a]
;  W = [b,a]
;  W = [a,b]
;  W = [b,b]
;  W = [a,a,a]
;  W = [b,a,a]
;  W = [a,b,a]
;  W = [b,b,a]
;  W = [a,a,b]
;  W = [b,a,b]
;  W = [a,b,b]
;  W = [b,b,b]
;  W = [a,a,a,a]
;  ... .

how does a more compact definition of word/1 look like, otherwise identical w.r.t. termination and the set of solutions, fairness, with the following constraints:

1. No use of built-ins like (=)/2.

2. No use of control constructs like (',')/2 or (;)/2, or call/1.

3. Uses one fact, one recursive rule, and one rule for word/1.

Maybe simpler is to ask for the terms F1 ... F4 in:

word(W) :-
   p(F1).

p(F2).
p(F3) :-
   p(F4).

For the record: The property exploited here is closely related to the undecidability of termination of a single binary clause. Praise goes to:

Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier, and Jörg Würtz. One binary horn clause is enough STACS '94.

Answer 1

The solution I have come up with is:

word(W) :-
        p([[]|Ls], Ls, W).

p([W|_], _, W).
p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :-
        p(Ws, Ls, W).

Sample query and answer:

?- word(W).
W = [] ;
W = [a] ;
W = [b] ;
W = [a, a] ;
W = [b, a] ;
W = [a, b] ;
W = [b, b] ;
W = [a, a, a] ;
W = [b, a, a] ;
W = [a, b, a] ;
W = [b, b, a] ;
W = [a, a, b] ;
W = [b, a, b] ;
W = [a, b, b] ;
W = [b, b, b] ;
W = [a, a, a, a] ;
W = [b, a, a, a] ;
etc.

I am using a difference list to incrementally materialize the solutions I want the toplevel to report.