MINIMUM CONSISTENT FINITE AUTOMATON

Next: LONGEST COMPUTATION Up: Automata Theory Previous: Automata Theory Index

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

Viggo Kann
2000-03-20