home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1903 < prev    next >
Encoding:
Internet Message Format  |  1992-09-09  |  1.9 KB
  1. Path: sparky!uunet!stanford.edu!rutgers!netnews.upenn.edu!saul.cis.upenn.edu!dawar
  2. From: dawar@saul.cis.upenn.edu (Anuj Dawar)
  3. Newsgroups: comp.theory
  4. Subject: A question about finite automata
  5. Keywords: finite automata, languages
  6. Message-ID: <88403@netnews.upenn.edu>
  7. Date: 10 Sep 92 01:39:53 GMT
  8. Sender: news@netnews.upenn.edu
  9. Organization: University of Pennsylvania
  10. Lines: 35
  11. Nntp-Posting-Host: saul.cis.upenn.edu
  12.  
  13. I have a problem relating to finite automata that I would appreciate 
  14. help with.
  15.  
  16. Let A and B be two non-deterministic finite automata, each with n 
  17. states, over the same alphabet.  It is easy to see that if they 
  18. agree on all strings of length at most 2n, then they accept the same
  19. language.  However, the automata that I am interested in have some 
  20. special properties, and I was wondering if these constraints could 
  21. be used to reduce that 2n bound (I am particularly interested in 
  22. obtaining a sub-linear bound).
  23.  
  24. The relevant properties are:
  25.  
  26. 1) Every state is a final state, i.e. the languages accepted are
  27. prefix closed.
  28.  
  29. 2) A and B can be seen as two copies of the same automaton, differing
  30. only in the choice of starting state.  In other words, I am actually
  31. interested in the equivalence of states, rather than that of automata.
  32.  
  33. 3) There is a constant k, such that the transition graphs of the automata
  34. have diameter k, i.e. there is a path from any state to any other state
  35. of length at most k.  Recall that the automata are non-deterministic.
  36.  
  37. My intuition suggests that 1 and 2 would not make much difference, except
  38. for getting rid of the factor of 2, but the third constraint might help.
  39. I would appreciate any help, or any pointers to literature that might be
  40. relevant.
  41.  
  42. Note: I am not particularly interested in the computational complexity
  43. of determining equivalence, but in an upper bound on the length of the
  44. shortest string that will distinguish two states.
  45.  
  46.  -Anuj Dawar
  47.   dawar@saul.cis.upenn.edu
  48.