MINIMUM CONSISTENT FINITE AUTOMATON

• INSTANCE: Two finite sets P, N of binary strings.

• SOLUTION: A deterministic finite automaton $\left(Q,\{0,1\},\delta,q_0,F\right)$ accepting all strings in P and rejecting all strings in N.

• MEASURE: Number of states in the automaton.

  
  

• Bad News: Not approximable within 2$-\varepsilon$ for any $\varepsilon >0$ [444].

• Comment: Transformation from MINIMUM GRAPH COLORING. Not approximable within $(\vert P\vert+\vert N\vert)^{1/14-\varepsilon }$ for any $\varepsilon >0$ [403].

• Garey and Johnson: AL8