wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

learning_dfa (527B)

      1 # Learning DFA
      2 
      3 https://cs.stackexchange.com/questions/19687/smallest-dfa-that-accepts-given-strings-and-rejects-other-given-strings
      4 
      5 https://cstheory.stackexchange.com/a/1858/
      6 
      7 [gold1978complexity]: the following problem is [NP_hard]:
      8   - given sets of strings P and N and number k
      9   - decide if there exists a [DFA] with at most k [states] that accepts all strings in P and no string in N
     10 
     11 Also [angluin1978complexity]
     12 
     13 Also [lingg2024learning] on binary alphabets
     14 
     15 Up: [machine_learning], [automaton]
     16 
     17 Aliases: DFA learning