% fringe(Tree,List) -> succeed iff List == fringe of Tree
% Eric Auer 12 maart 2002

fringe([],[]).                           % empty tree

fringe(leaf(X),[X]).                     % a leaf on the tree

fringe(node(_A,Ls),Xs) :- fringe(Ls,Xs). % descending

fringe([L|Ls],Xs) :-          % not a tree but a list of them
  append(Xs1,Xs2,Xs),         % nondeterministic!
  fringe(L,Xs1),
  fringe(Ls,Xs2).             % trying to compose the list

% ---------------------------------------------------------

atree( node(s, [node(np,[node(det,[leaf(a)])
               ,node(n,[leaf(program)])
               ,node(optrel,[]) ])
      ,node(vp,[node(iv,[leaf(halts)]) ]) ]) ).

sentence(1) :- atree(X), fringe(X, [a, program,halts]).

sentence(2) :- atree(X), append([X], [node(q,[leaf(r)])], Z),
  fringe(node(s,Z), [a,program,halts]).

sentence(3) :- atree(X), fringe(X,[a,program,halts,never]).