function monoid_equiv_rel(S,STR)

% go thru the nonempty strings
% try to concat them to get longer strings
% if concat is not in STR then it's an equivalence relation

DONE = {};

for i=2:length(STR)
    for j=2:length(STR)
        str = [STR{i} STR{j}];
        %if (length(str)>length(STR{end})),break; end
        if ~ismember(str,STR) % not an "element" of the monoid
            if ~ismember(str,DONE)
                if irreducible(str,DONE)
                    k = S(i,j);
                    fprintf('%s=%s \n',str,STR{k});
                    %else
                end
                DONE{end+1} = str;
            end
        end
    end
end
return

function b = irreducible(str,DONE)
% no element of DONE is a contiguous substr of str
b = 1;
for i = 1:length(DONE)
    sub = DONE{i};
    b = isempty(findstr(['@' str '@'] ,sub));
    if ~b, break; end;
end
return