function [U,w,MU] = findptsep(M)

alf = M.ALF;

X = simple_paths(M);
X = lensort(X);

U = {};
MU = {};
w = [];

w(1) = b2y(run_dfsa(M,''));
U{1} = '';
MU{1} = shuf2dfsa('',alf);

%DONE = X(1);
%STIL = X(2:end);
while ~isempty(X)
  x = X{1};
  [U,w,MU,b] = add_feature(U,w,MU,M,x);
  if ~b
    % make sure X saturates U
    %X = saturate(U,[DONE(:); STIL(:)]);
    X1 = saturate(U,alf);
    X = unique([X1(:); X(:)]);
  else
    X = X(2:end);
  end
  fprintf('%d strings left \n',length(X));
end
return

function X = saturate(U,alf)
N = length(U);
X = {};
PROGstart(2^N-1,'saturating...');
for i=1:2^N-1
  setstr = dec2bin(i,N);
  ii1 = find(setstr=='1');
  A = U(ii1);
  MA = AB2M(A,alf);
  B = setdiff(U,subs(A));
  MB = AB2M(B,alf);
  % x must contain all the features of A
  % and none of B
  Minter = intersects(MA,alf);
  Munion =     unions(MB,alf);
  MAlessB = diff_dfsa(Minter,Munion);
  [b,x] = accept_str(MAlessB);
  if b
    X{end+1} = x;
  end
  PROGupdate(i);
end
PROGend
return

function M = unions(MM,alf)
M = null_dfsa(alf);
for i=1:length(MM)
  M = union_dfsa(M,MM{i});
end
return

function MM = AB2M(AB,alf)
MM = {};
for i=1:length(AB)
  MM{i} = shuf2dfsa(AB{i},alf);
end
return

function M = intersects(MM,alf)
M = all_dfsa(alf);
for i=1:length(MM)
  M = intersect_dfsa(M,MM{i});
end
return


function S = subs(A)
S = {};
for i=1:length(A)
  Si = all_subseq(A{i});
  S = unique([S(:); Si(:)]);
end
return

function X1 = lensort(X)
LL = zeros(size(X));
for i=1:length(X)
  LL(i) = length(X{i});
end
X1 = [];
for l=0:max(LL)
  ii = find(LL==l);
  Xii = sort(X(ii));
  X1 = [X1; Xii(:)];
end
return

function [U,w,MU,b] = add_feature(U,w,MU,M,x)
xi = embedX(x,MU);
yh = sign(xi*w);
yt = b2y(run_dfsa(M,x));
b = (yh == yt);
if ~b
  % signs disagree
  N = length(U)+1;
  U{N,1} = x;
  %fprintf('processing x = %s \n',x);
  %MU{N,1} = bool2fsa_pt(['(' x ')'],M.ALF);
  MU{N,1} = shuf2dfsa(x,M.ALF);
  w(N,1) = yt * (1+abs(xi*w));
end
return

function xi = embedX(x,MU)
xi = zeros(1,length(MU));
for i=1:length(xi)
  xi(1,i) = run_dfsa(MU{i},x);
end
return



function M = str2M(M0,s,s00)
A = selfloops(M0,M0.q0);
R = '';
if ~isempty(A)
  R = [R setstar(A)];
end
if ~isempty(s)
  q = M0.q0;
  for i=1:length(s)
    s1 = s(i);
    if s1~='@'
      R = [R s1];
      q = dfsa_delta(M0,q,s1);
    else
      q = dfsa_delta(M0,q,s00(i));
    end
    A = selfloops(M0,q);
    if ~isempty(A)
      R = [R setstar(A)];
    end
  end
end
M = gregexp2dfsa_fast(R,M0.ALF);
return