function b = is_krev(A,k)
% is the fsa A k-reversible?

if (fsa_type(A)=='d')
  A = d2nfsa(A);
end

b = is_kdeter(A,0);
if b
  Ar = rev_fsa(A);
  b = is_kdeter(Ar,k);
end

return



function b = is_kdeter(A,k)
b = 1;
init_kfol(A,k);

for q=A.Q
  for s=A.ALF
    R = nfsa_delta(A,q,s);
    pairs = generate_combs_g(R,2);
    for i=1:size(pairs,1)
      q1 = pairs(i,1); q2 = pairs(i,2);
      kf1 = list_kfollowers(A,q1,k);
      kf2 = list_kfollowers(A,q2,k);
      S = intersect(kf1,kf2);
      b = isempty(S);
      if ~b
	%fprintf('q1=%d  q2=%d \n',q1,q2);
	%fprintf('%s\n',char(S))
	break
      end
    end
    if ~b, break, end
  end
  if ~b, break, end
end
return


function kf = list_kfollowers(A,q,k)
global KFOL
% KFOL{q,k} are the k-followers of q
if ~isequal(KFOL{q,k+1},{-1})
%if ~isequal(KFOL{q,k+1}{1},-1)
  % already computed this value
  kf = KFOL{q,k+1};
else
  kf = {};
  [qq1,ss1] = get_ndelta(A,q);
  for i=1:length(qq1)
    R = qq1{i};
    for r=R
      kf1 = list_kfollowers(A,r,k-1);
      for j=1:length(kf1)
        kf1{j} = [ss1(i) kf1{j}];
      end
      kf = [kf kf1];
    end
  end
  kf = unique(kf);
  KFOL{q,k+1} = kf;
end
return



function init_kfol(A,K)
global KFOL
% KFOL{q,k} are the k-followers of q
KFOL = {};
for q=A.Q
  KFOL{q,1}{1} = '';
  for k=2:K+1
    KFOL{q,k} = {-1};
  end
end
return