function S=dfsa2monoid(A)
% computes the syntactic monoid S of DFSA A
% S(i,j) = i*j

% though this isn't built into the definition of a DFSA,
% we're going to assume that Q=1,2,...,n w/o gaps

G = {};
G{end+1} = id(A);
for s=A.ALF
  x = sig_action(A,s);
  gind = findG(G,x);
  if ~gind
    G{end+1} = x;
  end
end

%now G consists of all the generators
%since we KNOW that the monoid is finite, 
%we can go ahead and apply the following "reckless" algorithm

S = [];
done = 0;
while ~done
  done = 1;
  for i=1:length(G)    
    for j=1:length(G)
      x = G{i};
      y = G{j};
      z = x*y;
      gind = findG(G,z);
      if ~gind
	done = 0;
	G{end+1}=z;
	S(i,j) = length(G);
      else
	S(i,j) = gind;
      end
    end
  end
end

return


function i = findG(G,z)
good = 0;
for i=1:length(G)
  if isequal(G{i}+0,z+0)  %doesn't work w/o unsparsing
    good = 1;
    break;
  end
end
i = i*good;
return


function x = id(A)
% the identity element of S(A)
x = speye(length(A.Q));
return


function x = sig_action(A,s)
% the action of the letter s on Q
n = length(A.Q);

x = sparse(n,n);

for q=1:n
  p = dfsa_delta(A,q,s);
  x(q,p) = 1;
end
return