XPost: comp.theory   
   From: sasha.mal@excite.com   
      
   Roger.Sindreu@gmail.com wrote:   
   > I would like to know all the methods you know for finding if two DFA's   
   > are equivalent.   
   >   
   > If possible, please give references.   
      
   Well, check that the languages of both A x B^c and  A^c x B  are empty.   
   X^c is any automaton which accepts complement of the language of X.   
   since your automata are deterministic (DFA), the complement is trivial   
   and constructing the product takes quadratic time. Emptieness check   
   takes linear time in the size of the product.   
      
   What is the complexity of the problem for NFAs?   
      
   Cheers   
   Sasha.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)