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

### MINIMUM CONSISTENT FINITE AUTOMATON

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

- SOLUTION: A deterministic finite automaton accepting all strings in P and rejecting all strings in N.

- MEASURE: Number of states in the automaton.

- Bad News: Not approximable within 2 for any [421].

- Comment: Transformation from MINIMUM GRAPH COLORING. Not approximable within for any [381].

- Garey and Johnson: AL8