% ack! this doesn't work! don't know how to find representation
% given a monoid's multiplication talbe... must think/ask people


function A=monoid2dfsa(S)
% converts a syntactic monoid S to a DFSA A
% A is determined up to initial & final states
% so really, the only relevant calculation is that of A.delta

% S is an NxN matrix of its multiplication table

[n,n] = size(S);

nQ = num_states(S);  % how many states must A have?
Q = 1:nQ;


% figuring out the number of letters in the alphabet 
% is a bit trickier

% we'll assume the elements of S are numbered 1:n
% and 1 is the identity element
% furthermore, we assume that S(i,j) = i*j

% essentially, we're looking for the minimum set of generators

GEN = [1];
done = 0;
while ~done
  % does the current GEN generate everything?
  S1 = [];
  for i=1:length(GEN)
    for j=1:length(GEN)
      k = S(i,j);
      S1(end+1) = k;
    end
  end
  D = setdiff(1:n,S1);
  if isempty(D)
    % GEN generates everything
    done = 1;
  else
    g = D(1);
    GEN(end+1) = g;
  end
end

% convert GEN to letters
ALF = abcdefghijklmnopqrstuvwxyz;
GEN = GEN(2:end)-1;
ALF = ALF(GEN);
A.Q = Q;
A.ALF = ALF;
A = init_ddelta(A);
for g=1:length(GEN)
  s = ALF(g);
  Q1 = S(g,:);
  A = set_ddelta(A,Q,repmat(s,1,n),Q1);
end

% this choice is arbitrary
% included for completeness only
A.q0 = 1;
A.F = [1];

return



function nQ = num_states(S)
% how many states must A have?

[n,n] = size(S);

% since each element of S is a function from Q to Q,
% we must have n <= nQ^nQ

nQ = 1;
while 1
  if (n<=nQ^nQ)
    break
  else
    nQ = nQ+1;
  end
end
return