function M0 = minimize_dfsa(M0)
% M1 is the smallest equivalent dfsa to M0
% see str2dfsa.m for basic dfsa definitions

%this follows the construction in Lewis and Papadimitriou, p 80

nQ = length(M0.Q);

% initialize the \equiv_0 relation
EQU = eye(nQ);
for p=1:nQ
  for q=p+1:nQ
    EQU(p,q) = (ismember(p,M0.F)==ismember(q,M0.F));
  end
end
EQU = EQU+EQU';

% compute \equiv_k for k=1:nQ
for k=1:nQ
  EQU1 = eye(nQ);
  for p=1:nQ
    for q=p+1:nQ
      b = EQU(p,q);
      for s=M0.ALF
	p1 = dfsa_delta(M0,p,s);
	q1 = dfsa_delta(M0,q,s);
	b = b & EQU(p1,q1);
	if ~b, break, end
      end
      EQU1(p,q) = b;
    end
  end
  EQU = EQU1 + EQU1';
end

% collapse equivalent states
for p=1:nQ
  for q=p+1:nQ
    if EQU(p,q)
      M0 = collapse(M0,p,q);
    end
  end
end
M0 = remove_unreachable(M0);
return


function M = collapse(M,p,q)
% everything that pointed to q must point to p

[qq0,ss0] = get_ddparents(M,q);
M = set_ddelta(M,qq0,ss0,repmat(p,[length(qq0),1]));

% if q is the start state then make p the new start state:
if (M.q0==q)
  M.q0 = p;
end

% now just zero out q:
% M = set_ddelta(M,repmat(q,[length(M.ALF) 1]),M.ALF,zeros(length(M.ALF),1));
% actually no need to do that -- q is now unreachable

% take q out of F if it's there
M.F = setdiff(M.F,q);
return